Recently I had some difficulties with an on-premise to Exchange Online mailbox move. This happened when executing the following command:

New-MoveRequest -Identity <mailbox> -remote -RemoteHostName “<on-prem-hybrid-fqdn>” -TargetDeliveryDomain “<tenant>.mail.onmicrosoft.com”

This resulted in the following error:
The operation couldn’t be performed because object ‘<mailbox>’ couldn’t be found on ‘<mbx>.prod.outlook.com’.
+ CategoryInfo : NotSpecified: (:) [New-MoveRequest], ManagementObjectNotFoundException
+ FullyQualifiedErrorId : [Server=<mbx>,RequestId=<id>,TimeStamp=<time>] [FailureCategory=Cmdlet-ManagementObjectNotFoundException] 70
F9A242,Microsoft.Exchange.Management.RecipientTasks.NewMoveRequest
+ PSComputerName : outlook.office365.com

After some research it was clear that the specific user had two mailboxes, one on-premise and one online. Both connected to a single user. This happened because the hybrid and AAD Sync configuration was created after the creation of some test mailboxes with overlapping UPNs. At the moment AAD Sync was operational these users where soft matched. At the moment I tried to move the mailbox to Office 365 it resulted in an error being unable to move the mailbox. So one mailbox had to be removed before being able to continue the mailbox migration for this user.

In my case the easiest way to overcome this was is to delete the online account completely and resynchronize this. The most important part is that you also have to remove the user from the recycle bin in Office365, otherwise it will be restored on the next AAD Sync operation resulting in the same situation as before. When the user is completely removed from Office 365 you are able to move the mailbox.

The following steps where taken out:
1. Do a full AAD Sync with Office 365;
2. Open an PowerShell connection to Office 365;
3. Enter the following commands:
– “Remove-MsolUser -UserPrincipalName <UPN>”
– “Remove-MsolUser -UserPrincipalName <UPN> -RemoveFromRecycleBin”
4. Do a full AAD Sync with Office 365;
5. Restart your mailbox move.