You've done well to clean off failed installs but I don't see where you reinstalled the install. Here's a link about that.
I've been reading through the posts on this subject and it seems there is no definitive answer. I have a windows XP box with SP 3. Once booted into Windows I immediately start getting Windows Installer trying to install something. Clearly there is a failed installation in there that windows installer keeps trying to install but can't. When try to intall something new I get the "This happens with windows in running in safe mode or windows installer is installed incorrectly" message. I tried installing windows installer 3.1, but it tells me it is already installed and quits. I tried installing the Windows Intaller Cleanup program that RProffit linked to, but then I get the windows installer is broken message and it can't install. Seems like I am in for a reformat and reload?