It sounds very much to me like the modus operandi of malware (especially since being initiated from a fresh boot).
Google for "superantispyware" and "malwarebytes antimalware", and scan the PC with each of those. You may find that the malware has been written to intercept the running of these though, but at least it should give an indication of the program not running properly (e.g. exiting immediately or not being able to start), which would further reinforce my hunch. Anyway, some ways around that are to rename the executable, and to boot in safe mode with command prompt (which doesn't execute any svchost processes usually), then run the program from the command prompt (not via explorer), and scan that way (remembering to update the package with the latest updates first).
Anyway, see how you go and report back?
