Native Move synchronization fails with the Recipient "<GUID>' isn't a mailbox" error (4255031)

Native Move synchronization fails with the Recipient "' isn't a mailbox" error

Native Move synchronization fails with the Recipient "<GUID>' isn't a mailbox" error

This happens when a Native Move collection is configured to migrate mailboxes cross forest from an Exchange Server 2007 to Exchange Server 2013 CU6.

Log Error Example:
VERBOSE: [08:35:41.794 GMT] New-MoveRequest : Processing object "$null".
VERBOSE: [08:35:41.825 GMT] New-MoveRequest : Recipient '108dfc1c-50ae-4379-8a92-02efcbd5eae3' isn't a mailbox.
VERBOSE: [08:35:41.841 GMT] New-MoveRequest : Admin Audit Log: Entered Handler:OnComplete.
Recipient '108dfc1c-50ae-4379-8a92-02efcbd5eae3' isn't a mailbox.
+ CategoryInfo : NotSpecified: (:) [New-MoveRequest], RemotePermanentException
+ FullyQualifiedErrorId : [Server=AQMM-T10R1-EX1,RequestId=0a3609d5-6dee-4a19-8d23-00c2d2a3aa8e,TimeStamp=9/12/201
4 8:35:41 AM] [FailureCategory=Cmdlet-RemotePermanentException] 9C5C44EC,Microsoft.Exchange.Management.RecipientTa
sks.NewMoveRequest
+ PSComputerName : XYZXYZ

The effect is caused by a problem that exists in Cumulative Update 6 (CU6) for Exchange Server 2013.

Please be advised that described behavior with New-MoveRequest failing for cross forest moves between Exchange 2007 and Exchange 2013 CU6 is a confirmed bug with Microsoft API used by our product, within MS local database. Unfortunately there is no public information available about the bug so far (From Microsoft) however it has already been scheduled to be fixed in CU7. It has been confirmed by Microsoft Program Management and Escalation teams.

Currently there’s no ETA for CU7.