Issues with Local Mailbox Moves on Exchange 2010 SP3

A customer running an Exchange 2010 SP3 UR15 multi-role server had issues moving mailboxes between databases.

 The error experienced was as follows:

Get-Mailbox "mailboxname" | New-MoveRequest -TargetDatabase "Mailbox Database Canada" -BadItemLimit 10

There are no available servers running the Microsoft Exchange Mailbox Replication service.
    + CategoryInfo          : NotSpecified: (0:Int32) [New-MoveRequest], NoMRSAvailableTransientException
    + FullyQualifiedErrorId : C7FE28BB,Microsoft.Exchange.Management.RecipientTasks.NewMoveRequest

Running Test-MRSHealth cmdlet to test the Mailbox Replication Service (responsible for processing mailbox moves) returns the following error on the environment.

RunspaceId : 4c95273c-3876-4369-86e3-1d9c90bc999e
Check      : ServiceCheck
Passed     : True
Message    : The Mailbox Replication Service is running.
Identity   : EXCHANGESERVER
IsValid    : True
 
RunspaceId : 4c95273c-3876-4369-86e3-1d9c90bc999e
Check      : RPCPingCheck
Passed     : False
Message    : The RPC endpoint for the Microsoft Exchange Mailbox Replication service couldn't respond: The call to 'net.tcp://exchangeserver/Microsoft.Exchange
             .MailboxReplicationService' failed. Error details: Access is denied.. --> Access is denied..
Identity   : EXCHANGESERVER
IsValid    : True

RunspaceId : 4c95273c-3876-4369-86e3-1d9c90bc999e
Check      : QueueScanCheck
Passed     : True
Message    : The Microsoft Exchange Mailbox Replication service is scanning mailbox database queues for jobs. Last scan age: 00:03:35.0822558.
Identity   : EXCHANGESERVER
IsValid    : True

Despite the error indicating Access is denied, all permissions were set correctly on the Mailbox Import Export role which was validated with:

Get-ManagementRoleAssignment -Role "Mailbox Import Export"

After further investigation, the following error was present:

 Log Name:      Application
Source:        MSExchangeIS Mailbox Store
Date:          13/10/2016 12:50:33 PM
Event ID:      7043
Task Category: IS/AD Interactions
Level:         Warning
Keywords:      Classic
User:          N/A
Computer:      Exchange.domain.local
Description:
The mailbox GUID of an external system mailbox ('Mailbox - SystemMailbox{1c3fa654-fe01-4041-a3a6-0444ca10f96c}') does not match the information in the Active Directory for the mailbox. The existing GUID ('8c0c971d-c5d7-495b-aff7-53356904789a: /o=Exchange/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=SystemMailbox{1c3fa654-fe01-4041-a3a6-0444ca10f96c}') has been replaced with the expected GUID ('ed55827e-7cdd-466e-9421-a0dbce5f6486: /o=Exchange/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=SystemMailbox{1c3fa654-fe01-4041-a3a6-0444ca10f96c}').

 

 The GUID of the SystemMailbox no longer matched the GUID of the Active Directory mailbox at the customer site.

To restore this, we ran "Setup /PrepareAD" from the Exchange 2010 SP3 setup media.  This restored the Exchange SystemMailbox association with Active Directory.

After running Setup /PrepareAD on the environment, we were able to move mailboxs again.