Hello BC community! I, too, was suffering from Google redirects (but strangely, only in Google Chrome, not in IE, so I uninstalled Chrome after the fix) for WEEKS before my AVG started detecting "Vundo.KA". It said it would heal, but did not, and detected this in several different system files and memory. I could also not reinstall Windows, and searched and searched for an answer. I found a malware removal guide on GeeksToGo.com on fixing "Google Redirects" that sanctioned the use of a rootkit remover AFTER backing up the registry, making a new system restore point and cleaning up temporary files. I went ahead and did all of that, ran the rootkit removing program, and sure enough, a nasty rootkit was found and cleaned off my system.
It is now good as new, and I'm posting this here just in case this info can help anyone with their computer problems (or help you fine BC Angels help others w/their PC problems- what a great source of help this website is!!!). I just used the "Personal Security" rogue malware removal guide here after clicking on an image on a Google image search took me to a website/pop-up which got me infected with THAT- THANK YOU!!!
Sorry if this wasn't posted in the correct forum, but it seems to be such a common issue, I want to get the info out to everyone who may find it of use!