So you’re cleaning out a storage group, and there are a bunch of mailboxes that you don’t seem to be able to move?

If you check the Eventlog, do you find these events?

The MAPI call ‘OpenMsgStore’ failed with the following error:
The information store could not be opened.
The MAPI provider failed.
MAPI 1.0
ID no: 8004011d-0289-00000000

For more information, click http://www.microsoft.com/contentredirect.asp.

Failed to open mailbox ‘/o=CONTOSO/ou=First Administrative Group/cn=Recipients/cn=JohnDoe’ in mailbox store ‘/o=CONTOSO/ou=First Administrative Group/cn=Configuration/cn=Servers/cn=ContosoMailServer/cn=Microsoft Private MDB81234567’ on server ‘ContosoMailServer’.
Error: The information store could not be opened.
The MAPI provider failed.
MAPI 1.0
ID no: 8004011d-0289-00000000

For more information, click http://www.microsoft.com/contentredirect.asp.

Quickly check if these users are not disabled.  Mailboxes with disabled users as associated account cannot be moved.  The workarounds are to enable the user accounts – which is not that desireable for your company’s Security staff – or assign SELF as the associated account.

More info at Microsoft.