Exchange 2013 Deleted Mailbox Not Present In GUI

When you delete/disable a mailbox in Exchange, it won't show up in the Exchange Admin Center (EAC) until the server maintenance runs on it's schedule.
If you have someone delete a mailbox when they shouldn't have, you might need to reconnect the mailbox sooner than the schedule allows.

The Clean-MailboxDatabase cmdlet from Exchange 2010 no longer works in Exchange 2013.

The new cmdlet is Update-StoreMailboxState which, in theory, allows you to update a single mailbox state instead of the entire database.

I was having trouble getting a disabled mailbox to show up after running the command (several times) but I finally found one that works.

What didn't work:

Get-MailboxStatistics -Database “DBName” | Where {$_.DisconnectReason -ne $null } | ForEach { Update-StoreMailboxState -Database $_.Database -Identity $_.MailboxGuid -Confirm:$False}

The above command specifies only disconnected mailboxes, which for some reason didn't grab an recently disabled mailboxes; it just showed mailboxes deleted a week ago or longer.

What did work:

Get-MailboxStatistics -Database "DBName" | ForEach { Update-StoreMailboxState -Database $_.Database -Identity $_.MailboxGuid -Confirm:$false }

**Note** Change "DBName" to match your environment.

This command updates all mailboxes on the specified database; it does take a bit longer depending on the size of your database but it actually worked, so it was worth the extra few minutes.