Ran into this even though there wasn’t any mailboxes (as far as I could see)

Used this method

Method 4: Use Active Directory Users and Computers to search for mailboxes that are on a mailbox store

//

1. Start Active Directory Users and Computers.
2. Right-click the domain that you want, and then click Find.
3. Click the Advanced tab, click Field, point to User, and then click Exchange Home Server.
4. In the Condition list, click Ends with, type the name of the Exchange computer, and then click Find Now.
5. If you are prompted to add the current criteria to your search, click Yes.
6. When you have identified which users have mailboxes on this store, you can use Active Directory Users and Computers either to move the mailboxes to a different store or to delete the user’s mailbox.

The mailbox search results appear in the bottom pane.

From here to see that there was still one mailbox left.

http://support.microsoft.com/?id=279202