Well if you do a clean install on a formatted hard drive (Which can be done using the upgrade disk) Then it should be fine. Clean Install with a Upgrade Windows 7 Version
Before going down that route though, you want to make sure of the procedure and backup all your files and make sure that you have all the upgrade information necessary before starting. It's not trivial, and there is the danger of ending up with no working system at all without more work if something goes wrong
But it sounds like you have exhausted a lot of other fixes already... I'd plug away at it a bit more if possible, more net searches, then reserve the reinstall when there's nothing left to try.
I don't normally recommend using CCCleaner as it has the potential to do harm, but in this case, there is the possibility that it may clean out bad registry entries related to the installs of the redistributable packages and the bad uninstall entries for them. Might give that a shot... google CCCleaner.