You have tried everything you could find on the Internet about fixing this problem, but nothing seems to work. But you may have missed one solution which is not talked about much.
Just open regedit and go to
You will find a DWord value called Attributes. If its data is 0x00100024, this is causing the problem. You should change to 0x00000024 or just 24 (hexadecimal).
If you're afraid to mess with the Windows registry, or are not a tech savvy computer user, you can use a file that will automate the process for you. It also includes all the other solutions you may have already tried, along with the one mentioned above. This page here has a tip #100 which is quoted below. Merge the .REG file to automate the process, then Refresh the desktop to get the icon.
100. Restore the missing Internet Explorer icon to the Desktop in Windows XP (link to a .REG file)