Whenever you delete a mailbox from Exchange 2010 the mailbox is not deleted completely from the server.
To remove the mailbox you have to execute the following commands:
Clean-MailboxDatabase "Mailbox Name"
When you now open Exchange Management Console and go to Recipient Configuration and then Disconnected Mailboxes you will see the the mailbox you just deleted there.
To now delete all mailboxes with the disconnected state you have to execute this command:
Get-MailboxStatistics -Database "Mailbox Name" | Where-Object {$_.DisconnectReason -eq "Disabled"} | ForEach {Remove-StoreMailbox -Database $_.database -identity $_.mailboxguid -MailboxState Disabled}