Icon Protection

There are several things you could do depending on how you want to do it.
1. you could copy the icons into all the respective user folders that way if one deletes an icon it is removed from his profile and not everyone elses. If there are several users or unexpected guest users than this may not be an option.
2. Use a script. you could have a logon script that copies the links back to the desktop.
it could be something like: "if not exist c:\folder\desktop\file copy c:\folder\file c:\folder\desktop\file" Now that may be slightly over simplified but the format should work. There may be other ways but im not a script person.
3. You might could use group policies. You could try runing gpedit.msc from run command and looking through there for a way to keep them from deleting the icons.

These seem to be the most obvious/easiest ways of restricting icon deletion or at least replacement. You may also be able to tweak the registry but not sure where to point you.

Hope this is helpful.
Jason