Renaming them to anything.  For example, renaming "Internet Explorer" to "sad;lj".  I have a client whose kids keep renaming the icons on their windows 98 desktop.  I dont want to lock the computer using a program like Clean Slate or Deepfreeze, just disable icon renaming.