Error: The operation couldn’t be performed because object ‘User’ couldn’t be found on ‘*.prod.outlook.com’.
This error tells us that the Move Request can’t find a user in Office 365 Exchange Online with an object-id matching the mailbox you are requesting to move.
It can be several reasons to this to check these first:
User has the right principal name – Often you have to change your principal name to match your external domain name in order to have ADFS work. If this haven’t been synced to Office 365 it will not necessary have the right principal name and object-id. See Office 365 Tenant Administration under Users.
And if it all looks good, but still get the message you can delete/remove the user from Office 365 and make the DirSync sync the user again.
Logon to Office 365 with Powershell and Azure Cmdlets. Need to be a Global Administrator.
Remove-MsolUser -UserPrincipalName email@example.com -RemoveFromRecycleBin -Force
Now you need to rerun DirSync or wait for the next scheduled sync.