Exchange – Your Exchange Server administrator has blocked the version of Outlook that you are using…?

Interesting issue came up today. While trying to demo the use of a registry key called "DumpsterAlwaysOn", it seems I was unable to open any mailbox in the Exchange organization using Microsoft Office Outlook 2003. It always showed:

Using Microsoft Office Outlook 2007 I had no problem...so...maybe there was something blocked by the Exchange Server administrator, but when checking this using the Exchange Management Shell, nothing was blocked...

The reason the issue was raised soon became clear. There were no Public Folder stores anymore in the Exchange organization. After creating a new Public Folder store, I was able to login using Outlook 2003, add the registry key of DumpsterAlwaysOn and recover shift-deleted items from the inbox...