|I know I'm jumping into this thread late. I hope you solved your problem already, but if you haven't...|
It sounds like you have W32/Alureon Trojan (AKA Google Redirect Virus [TDL]) or some variant. It's relatively new and stealthy as all get-out. Malwarebytes, CDFix, Sophos Anti-Rootkit, GMER anti-rootkit, Microsoft Security Essentials, ComboFix & Spybot Search & Destroy 1.62 FAILED to pick up on it; and Hijack This! logs appeared clean. (McAfee didn't notice it either, but that doesn't surprise me <snicker>).
The only thing that killed it was a product called Hitman Pro (the version I used was 3.5), you can find it on CNET.Com or from their page here:
http://files.surfright.nl/HitmanPro35.exe. It's free for 30 days; it only needed 10 minutes to clean this machine. Also, Microsoft has an article about it here:
http://www.microsoft.com/security/portal/Threat/Encyclopedia/Entry.aspx?Name=Win32/Alureon if you want to take a shot at manual removal.
Hope this helps!