Search results being corrupted

I recently cleaned a badly infected machine – all is good now except one thing: All search results from Google are being corrupted. On every results page the first 8 or so are items completely unrelated to the search. I have checked the system with Symantec Corporate Anti-virus, spybot S&D, PCTools Spyware Doctor, Ad-Aware SE, Windows Defender, Kaspersky online and Trend Micro Housecall online. None of them found any problems. I looked at the BHO’s and toolbars and disabled everything, but still the same problem.

Anyone have some suggestions on where to try next?

Thanks,
Scott