In exchange 2007 and exchange 2010, when a user is deleted the disconnected mailbox list is not refreshed, so if you need to reconnect a mailbox you cannot.
The quick way to refresh this is via powershell. Drop to a powershell prompt and enter the below, entering your mailbox database name
clean-mailboxdatabase <mailbox database name>
Job done.