You might need to check for rootkits.

http://www.sysinternals.com/Utilities/RootkitRevealer.html

What tools have you tried? Some that I recommend are Spybot Seach and Destroy, AD-Aware SE, Hijack This, Microsofts Antispy.
As for a virus scanner NOD32 is more than 5 times fasters than any other scanner and it detects/cleans more than the others.

If you can't get it off I can ship you an ultimate boot cd.