Came across this when trying to uninstall an Exchange server (was the original server in the organisation). I knew there were no mailboxes left in the database indicted in the error message but it seems there are hidden mailboxes.
You need to run through the following commands and make sure you don’t get any results back:
Get-Mailbox -Database <mailstore name> Get-Mailbox -Archive -Database <mailstore name> Get-Mailbox -PublicFolder -Database <mailstore name> Get-Mailbox -Arbitration -Database <mailstore name>
This last one was my problem. I had to move these mailboxes off to the other server which was a case of simply piping the result and adding a move request to it:
Get-Mailbox -Arbitration -Database <mailstore name> | New-MoveRequest -TargetDatabase <new mailstore name>
Once complete clear up the requests either from the PowerShell command line or within the GUI.