We had this problem too.

Off the top of my head we did something like this.

We moved the "Create New Shortcut" wizard(which I think is AppWiz.cp) to an area the students didn't have access to, only ourselves(admins) and Staff. If the students tried to do New|Shortcut, they get an access denied message.

I'm trying to remember what the registry key was that needed to be changed the tell it to look somewhere other than C:\windows.

When I do. I'll let you know

We also disabled RightClick (another regedit) which helps.

The problem we have with shortcuts now, is kids bringing them in on Floppy, and using hyperlinks in Word!!