Outlook recently stopped connecting to my Exchange 2003 server with an 0x8004011D error. There were no errors in the server's event logs, and oddly enough all web-based access worked (Outlook Web Access, RPC over HTTPS).
As it turns out, the fix was pretty easy - you just need to delete the Exchange profile on the machine. (Not, as mentioned in comments below, the USER profile - just the EXCHANGE profile).
The easiest way to do this is to right-click on the Outlook icon in the Start Menu and open the Properties window. (You should see the screen below).
Click on the "Show Profiles" button and you will open the window below.
Then click "Remove". The next time you run Outlook you will see the initial setup wizard again.
Note: You have to delete the entire profile - if you delete just the mail server from the profile the problem doesn't go away. Hope that saves someone else some time and energy...
ETA: You may also be able to do this by running Outlook with the /firstrun switch - though I haven't confirmed whether this actually deletes the profile and resolves the issue. I haven't been able to reproduce this issue since on either Outlook 2003 or Outlook 2007.