I have problems with users wanting to cut and paste data in the cells. How do
I protect a worksheet to keep someone from "cutting" an unlocked cell and
pasting it in another "unlocked" region. They destroy the formatting such as
borders, backcolors, etc. and make quite a mess. I would like to retain the
ability to copy the contents of the cell but not the formatting.

Show them about "Paste special". when you right click you'll find that
option righ below Paste. So select paste special then select Values.
Another way to do is it trough VBA by recreating the right click menu.