OK, I finally broke down and approved the IE 8 update on my WSUS update. It installed fine on about 50 computers but one computer is having a major problem installing. It installs with no errors and ask for a reboot. Once I reboot I try to open IE, and it still opens IE6. I had to delay the IE 7 update on this computer because our bank was not compatible with IE 7 when it was released. Also, The Internet link in the start menu is broken. It has no IE icon and when i click it, it says Access Denied. Also, when I try to navigate to another page when IE 6 is open it's saying the file extension needs to be registered, but it does go to the website. I tried to uninstall and install IE 7 and got the same problem. I went to Microsoft's website and did their 8 step process and nothing worked. I'm going to include a screenshot. It's weird how the browser is IE 6, but the settings are IE 8 settings. (notice the tab settings).
Download the update locally to the PC from MS (not through WSUS). reboot the box and begin the install. On a pc I saw this on, IE6 Actually went through an uninstall process before I could install IE8.
I wouldn't bother troubleshooting this one any more - just re-image the machine. You've already spent a lot of time on it, and it's a question of how much longer it will take you to resolve it vs how much time it would take to re-image.
It's possible that this PC may have some misbehaving 3rd party software on it. I've seen that happen a few times, and chances are that if the software is misbehaving in this sense it will also misbehave in others, e.g. if you try to remove it.
I've also seen upgrades not take properly when things are done in a certain order, e.g. some of our developers had originally upgraded themselves manually to IE6 at one time, and it caused all manner of havoc when it came time to do an automated update.
Overall I tend towards the view that if a problem is taking longer than half an hour or so to resolve, you really should be considering the re-imaging option. Your time can be more productively spent doing things other than troubleshooting a single cranky PC.