I'm running Outlook 2002 with Exchange 2000. All OS/Office updates and patches are installed.
I also followed Microsoft's advice from their knowledgebase. I still get this error. Here is what Microsoft suggested:
Error Message When You Receive New Mail
View products that this article applies to.
This article was previously published under Q329936
When new mail arrives in your mailbox, you may receive the following error message:
Sending and receiving reported error "0x80004005" : The operation failed.
This issue may occur if the script-blocking feature of Norton AntiVirus interferes with the new-mail announcement in Outlook.
To resolve this issue, use one of the following methods:
Disable Script Blocking in Norton AntiVirus
In Norton AntiVirus, turn off the "Enable script blocking" feature.
Disable New-Mail Notification in Outlook
To disable new-mail notifications:
In Outlook, click Options on the Tools menu, and then click the Preferences tab.
Click E-mail Options, and then click to clear the Display a notification message when new mail arrives check box.
Click OK two times.