Check to see that you're not using Roaming Profiles with a Folder Redirection GPO. If so, when the user deletes the shortcut, they're deleting the server copy. Then, when they log off, the workstations synchronize the two profiles by uploading the local copy to the server, replacing the deleted icons.