Same with me, congratulation~ Ready to re-install the operating system. I tried to fix the problem for one week but no fxxking solution. I thought the problem caused by 3-party software who can manage the Register Settings, like: UrUninstall 2005 or RegCleaner. So I don't install them anymore. For your information.
can you still run the program from these shortcuts? if you can then its just the icon path missing, just press the shortcut icon and click right button then select properties. On that windows choose shortcut tab and you will find change icon button, press this button and change the application path for this program. This will recover the icon onto the desktop.....
The guy in google is possibly facing a virus infection problem, maybe you can run an online virus to check for viruses and spyware. The below line is free and online virus scanner. But to clean all spyware you will need an official virus software. Good luck