desktop shortcuts

Hi
I have locked down a machine as tightly as I can thru gpedit but I still have the problem that I need to place shortcuts in all desktops and I encounter that some of my users will delete them. Since I placed the shortcuts in the “all users\desktop” folder any time somebody deletes a shortcut it’s gone for everybody.
Any suggestions on how to avoid or deny permission to users to delete those shortcuts? I tried changing permissions at the folder level but that didn’t seem to work…
Thanksfor any suggestions…