Exchange account was deleted/removed

You need to enable the account in AD and then you have to reconnect the mailboxes from Exchange Management Console-->select the Disconnected Mailbox option and reconnect it.

that's the problem. The users mailbox doesn't show in the disconnected list.

If you have backup then you can restore the same.

That's my fallback, but why wouldn't it show in disconnected mailboxes

any way to find out what DB the mailbox was on. We have many,many mail stores.

You can run message tracking against the old message tracking logs and find out to which database message was delivered

get-messagetrackinglog -Recipients:user@domain.com -EventID "DELIVER" -Start "05/02/2013 02:40:00" -End "06/02/2013 02:50:00" | FL Sender,Recipients,EventId,ServerHostName

You can get the server name and then you can run Clean-MailboxDatabase against that server. Yes you still need to run the command against all the database hosted on that server.

You can narrow down the search using
get-mailboxdatabase -server servername | clear-mailbox

hope that helps

Regards
Navdeep [v-2nas]
Infrastructure Sol. Architecture
[ExchangeADTech]

This is not the exact command but will give you list of all disconnect mailboxes.

http://www.howexchangeworks.com/2009/10/task-get-list-of-disconnected-mailboxes.html

Then you can filter for your MB.

So I ran the command:

get-messagetrackinglog -Recipients:user@domain.com -EventID "DELIVER" -Start "05/02/2013 02:40:00" -End "06/02/2013 02:50:00" | FL Sender,Recipients,EventId,ServerHostName

change the user@domain.com and adjusted the date to search for 01/22/2013 and end at 02/04/2013

and it found nothing.

Shouldn't it have found messages?