Recover Deleted Public Folder from Exchange 2003

Q: Customer contacted us to say that a public folder with over 1,000 items had vanished.
A: We were able to recover it as a deleted item using Outlook.

1. Open Outlook
2. Navigate to Public Folders
3. Click the parent folder deleted folder
4. Click Tools, "Recover Deleted Items" 
5. 
6. It showed the folder that had been deleted.
7.  
8. Select the folder, click the second icon in the toolbar "Recover Selected Items"

We found this link on Google and it has a much more details explanation of Exchange settings etc.

windows xp outlook 2003 "messaging interface has returned an unknown error"

Customer has Windows XP SP3 Running Outlook 2003.
Outlook 2003 was attached to Hotmail (pre-connector) and it worked until very recently.
When it stopped working the hotmail profile was removed & the Outlook connector was installed. Suddenly they could now access hotmail but their local pop3 account stopped to function.

the message we see begins when you click new, once outlook is open, "The Messaging interface has returned an unknown error"

So far i've tried:
1) repairing outlook
2) remove contents of MAPI32 folder & allowing Outlook to rebuild it
3) Register ole32.dll
4) Perform all pending updates
5) Uninstall Outlook Hotmail Connector