Well, there are two things really left for you to do;
SFC /SCANNOW Command - System File Checker
and
Repair Install
I have several question for you - Was this an upgrade installation or a clean installation of windows? Did you use any type of hack/patch to your OS installation? Like the "remove watermark" patch? If this was an upgrade install, that would be the key why this suddenly showed up as remnants of the old OS registry might have been corrupted or some other stuff messed up. Now, if there were patches/hacks done to the system, especially the "remove watermark" patch, it has been reported that system behavior and stability becomes compromised with the use of this tool.
Well, since you already spent so much time in trying to find the solution to this problem, might not be a bad idea to just go ahead and do a clean install.
Let us know your progress