This fix is for EX2007 – not sure if it was the same for EX 2003….”When you delete a user account and the related mailbox, the mailbox is retained as a disconnected mailbox according to the retention setting”
If you recreate the user account in AD, you should then be able to go into Exchange Management Console, expand the Recipient Configuration Node, and find the Disconnected Mailbox node. Look for the user name you want, right-click and choose Connect – which will start a wizard. On the mailbox settings page select Existing User, and your recreated account should be there to attach to – just make sure you don’t associate any mailbox to it while you are recreating the account.
Hope this helps!