Do you know what the Virus' name is? Because I had one similar to this, called winlogon.exe, that would do the same thing: redirect google searches; it eluded my AVs completely; completely denied any attempt to get into Safe Mode.
How I did notice it however, was via TeaTimer, a component of SpyBot S&D. It's a very useful thing to have installed, if only for TeaTimer, a real time Registry change scanner that allows you to deny or accept any attempt to make changes to your registry.
Unfortunately, it'd try and add itself to startup every couple of seconds, and I decided to (VERY ANGRY ABOUT THIS) update SpyBot S&D and it got around TeaTimer.
I found a method of removal, but it was too late and it has pretty much bricked my windows HDD. I'm contemplating a reformat, but I'd lose 450GB of data. ;.;
Anyhow, you could try a google search for the name of this virus, and there are bound to be at least one removal tutorial, and a ton of other related but also helpful material to read over.
If you know components (or the virus itself), you can use HiJackThis, but only if you're positive you have all of the components selected, otherwise it may just reapply itself.