Hello, I'm new here but had a same problem with an XP PC of friends. No restaure, no user profile, no system informations.
I found a place (sorry, a french one) where they make diagnostics from the Hijackthis report ; they found a couple of trojan, registry keys to fix and sevices to de-activate.
I had to run EasyCleaner and Ewido but it worked perfectly !!!!
I had things like :\WINDOWS\System32\ winsystems.exe to be removed
I had to stop Services like : Norton AntiVirus Auto-Protect and ScriptBlocking Service
You can try sending your hijackthis report to :
http://forum.zebulon.fr/index.php?showforum=51
Good luck