I have never run across a beast like this before, Once I caught it every Google, Bing or Yahoo search would be redirected to a bunch of low rent ad sites. I finally wound up using Altavista search, which I suppose is such a minor search engine player they didn't bother hijacking it.
NOTHING would even detect it. Not Nortons, Kasperky, Super AV, Malware Bytes, etc. etc. I went through the whole PC Magazine list of top rated 2011 AV packages. There was a prior Google virus that Nortons and Kaspersky had made standalone removal tools for (Norton Power Eraser and TDSSkiller respectively), but these did not even detect the virus. Hijack this showed nothing suspicious.
I spent days on this problem. In using Altavista I finally sussed that it was a rootkit virus of some kind, and I finally came across this odd little anti-malware rootkit detector package (link below) called RegRun 6.9. The instructions had imperfect grammar, but by God it worked! It looked at the dlls and flagged a suspicious one and that was it. It worked where everything else had failed.
Edited by monkapotamus, 26 June 2011 - 02:25 PM.