In addition to your search bar redirecting, do you ever get pop-ups to illegitimate websites? Randomly, I'll get a pop-up to a random website (porno.com, etc.) which sometimes try to download trojans and such.
It's more annoying than anything. I've had this problem for a few weeks and there's no sign of any malware on my PC after running many tests.
Apparently there are already fixes for it for Firefox, but nothing for Chrome/IE that I've found yet.
Mod Edit: Split from: http://www.bleepingcomputer.com/forums/t/337423/internet-connection-and-search-result-problems-after-malware-removal/
Edited by Andrew, 05 August 2010 - 12:51 PM.
Split to It's Own Topic - AA