Thank you very much for this thread. It has helped me no end, and in that spirit I want to share what happened to me (and my own observations) in case it helps others. I may be talking too soon, but after breaking the habits of a lifetime I followed ALL recommendations at the start of this thread, in the order listed, and don't appear to have any more of these annoying redirects happening. The things I noticed.
1. Some time ago I updated to IE 8, did not like it and rolled back to IE 7. I disabled IE 8 from my automatic updates, and this disabled Automatic Updates completely. They weren't happening and I did not notice.
2. I was using the Windows Software Firewall on Windows XP Home Edition, plus AVG Pro, plus the hardware firewall in our router.
3. Over the past few days I noticed the odd behaviour beginning to occur with redirects from Google links but also the occasional pop-up (with pop-up blocker turned on).
4. I ran a full virus scan with AVG Pro (nothing), and ran an AVG Pro Root Kit Scan (nothing again).
5. I searched for Microsoft Updates, XP Updates etc, but whenever clicking on any of those links I was ALMOST ALWAYS redirected - often to a page which was a mix of Google results and Ask Jeeves results.
6. I did finally manage to get the Microsoft Updates page and downloaded the updates, leaving my PC run whilst I was away from it. I assumed (wrongly) that it had completed when I returned. No updates had been downloaded (as I now know).
7. I then came here, and followed all of the advice. Since then no redirects and all links to Microsoft pages from search results are working. I then downloaded and installed 46 waiting updates.
8. To make sure that the automatic updates continue to work I upgraded to IE 8 It's got problems, but at least my automatic updates will now work correctly again.
Thanks to everyone here for all of the help provided to me and I hope some of my observations may help others.