I started getting the following problem when moving mailboxes, even within the same server but between databases:

Warning: Failed to clean up the source mailbox after the move.
Error details: MapiExceptionUnexpectedMailboxState: Unable to delete mailbox. (hr=0x80004005, ec=2634)

Turns out it was caused by the Exchange 2010 SP2 RU3 update. Neither RU4 or RU5 v2 seems to solve it and it has been widely discussed here.

I just got confirmation from Microsoft that this is a known problem and is scheduled to be fixed in Exchange 2010 SP3 RU1. In the meantime, you’re asked to perform the following:

Get-MailboxStatistics –Database “dbname” | Where-Object {$_.DisconnectReason –eq “Softdeleted”} | ForEach {Remove-StoreMailbox –Database $_.database –identity $_.mailboxguid –MailboxState Softdeleted

To be contiuned…