While performing a test Mailbox move from one database to another using New-MoveRequest, the move status was shown as queued, upon looking at the Get-MoveRequestStatistics saw the following error.

Error: An error occurred while updating a user object after the move operation. --> Active Directory operation failed on DC.DOMAIN.COM. This error is not retriable.
Additional information: Insufficient access rights to perform the operation.
Active directory response: 00002098: SecErr: DSID-03150F94, problem 4003 (INSUFF_ACCESS_RIGHTS), data 0

The environment I was working in was very sensitive to permissions assigned to user. I did double check the user I am using to run the MoveRequest as appropriate permissions.

Also, I did notice, the Move is successful on some databases. Hence, I tried moving to all databases and noted where the Move is failing. The databases on which Move failed were mounted on mailbox servers other than the souce (where the mailbox resides).

For some reason I thought to check the “Exchange Trusted Subsystem” group membership. To my surprise the servers to which the Move was failing was part of the group.

Added the mailbox servers to the Group, Rebooted the servers and issue was fixed.