I'm running a similar problem. None of the microsoft pages or updates work. I can't remember if the error is the same. Can you download anything else from microsoft? Particularly messenger?
I'll try this later when I get to work on that computer:
I can download stuff directly from MS (reinstalled IE8 hoping that would do it). Haven't seen any symptoms of virus issues, but ran scans anyway. Tried Dial-a-fix too, nada. I haven't noticed any unusual activity via task manager.
I have read, however never had an instance with this issue but read that if you uninstall SP3 and reinstall it clears up. but again I never have done it...
Read this page: http://www.microsoft.com/communities/newsgroups it leads you to http://support.microsoft.com/kb/949377 where they say to ignore the title of the page and scroll down to the "advanced troubleshooting section" and follow "Method 1: Reset the registry and the file permissions" This page also shows you in the "More information" section how to determine whether a registry update failed.
Well, I finally just uninstalled/reinstalled SP3 and it seems to have fixed it.
Microsoft sent me a lengthly list of things to try, asking me to reply with the results - unfortunately the email kept bouncing. Thanks for all the suggestions!