Same issue is happening on my home XP Pro machine, and my dad's Windows 7 laptop. Both of ours started exhibiting this redirect behavior after we both had that "Security Shield" fake AV software pop up. We both removed it with MBAM run in safe mode, but this redirect behavior on Google searches still exists. Have scanned with MBAM, Spybot S&D, Symantec AV Corporate, all in safe mode, and none of them find any problems.
May have to just break down and reformat the darn thing. It's probably about time to do it again anyway.