Format cell borders on protected worksheet

[Beeblebrox]

I have a protected spreadsheet with some cells not protected so users can enter data. If they paste data from elsewhere, the cell border format is copied to. How can I allow users to change cell borders without having to use VBA? In protecting the sheet, I have checked to allow formatting cells.

[Ace_XL]

Uncheck the format cells when protecting the sheet.

[Beeblebrox]

That didn't work - cannot do any borders. I also notice that with all the format cells, rows, columns boxes checked, some of the border commands are available, e.g. Bold box, clear all, draw a border, but not some of the others like when putting borders around cells in a bunch.