Trying to move Exchange mailbox (via Console or Shell) fails with error:

Active Directory operation failed on [domain-controller-name]. This error is not retriable. Additional information: Insufficient access rights to perform the operation.

This may happen because inheritable permissions are disabled for the user (which is normal for domain admins). I experienced this issue with some old user accounts.

To resolve:
Open user account properties in Active Directory Users and Computers, change to Security tab > Advanced – check Include inheritable permissions from this object’s parents.

Once mailbox is successful moved you can revert the change.