Most exchange admins will run into this problem at some point. You do either one of the two actions – delete a user account using AD users and computers or remove the mailbox using EMC.
Once the account is deleted, the mailboxes are not deleted straightaway by default. They (should) appear in the Disconnected Mailbox section under Recipient Configuration in EMC. But, for some reason it doesn’t show up…
To correct this issue, you need to run a shell command. It will perform the same action as a “Run Cleanup Agent” in exchange 2003. The process will scan AD service for disconnected mailboxes that are not yet marked as disconnected in exchange store and update it.
Run Clean-MailboxDatabase “serverdatabase name”
If you head to the Disconnected Mailbox section now, there it is. The deleted mailbox!
You can connect it to a different user, permanently delete it or wait for exchange to purge it depending on your retention settings.