Windows 2003/2008 mixed AD environment with Exchange 2010 single server all roles.

The administrator was “trying” to fix an issue with logging in on some specialized third party software – it wouldn’t accept modified AD logins but would work if you deleted the user and recreated the same user. Unfortunately this led to a removal of the mailboxes as well.

Checked under Recipient Configuration to Disconnected Mailbox. Unfortunately it was only showing a much-older deleted user in there – none of the newly deleted/recreated users were listed.

clean-mailbox -identity "mailbox name"

Or this should also work piping them together:
get-mailbox | clean-mailbox

Then refresh your Disconnected Mailboxen – works like a charm.
I should really create categories for Exchange 2000/2003 and then 2007/2010, no?