Well, it wasn't only Google, but also Yahoo. I got rid of it eventually. It turned out to be spyware after all, and not the simplest kind. See this thread: The Most Complex Google Spoof Ever.

The CWShredder tool didn't work for me either, but the HijackThis.exe tool showed a few suspicious Browser Helper Objects (BHO). After I had them removed, my searches returned to normal. Nice IE-feature those BHO's, but with this type of spyware they're more trouble than they're worth.