I recently was working on an issue where an OnPremises Exchange Mailbox couldn´t be moved into Exchange Online (aka Office 365) via New-MoveRequest. The error message was "Target user 'XYZ' already has a primary mailbox". The solution to fix that was quite easy
The full error :
PS C:\Users\wieczorek.5> New-MoveRequest -Remote -RemoteHostName hybrid.emea.contoso.com -TargetDelivery
Domain contoso.onmicrosoft.com -RemoteCredential $ONPREMCREDS -Identity contoso.test
Target user 'Contoso Testuser' already has a primary mailbox.
+ CategoryInfo : InvalidArgument: (contoso.test:MailboxOrMailUserIdParameter) [New-MoveRequest], Targ
+ FullyQualifiedErrorId : [Server=AM4PR05MB3379,RequestId=0a954782-664b-401f-a9dc-7f54743f9dce,TimeStamp=06.07.201
8 21:49:32] [FailureCategory=Cmdlet-TargetUserAlreadyHasPrimaryMailboxException] C8F1378D,Microsoft.Exchange.Manag
+ PSComputerName : outlook.office365.com
The root cause here was that somebody enabled the Exchange Online feature and then created the Exchange OnPremises mailbox. This caused that the user had two mailboxes. One in the cloud, the other one in Exchange Online.
1.) As this user never used any office 365 features and didn´t got any emails in the cloud I decided to fully delete him in the cloud via:
remove-MSOLUser -UserPrincipalName email@example.com
remove-MSOLUser -UserPrincipalName firstname.lastname@example.org -RemoveFromRecycleBin
Keep noted the user might lose data if he had something already stored in the cloud if you perform these steps!
2.) After a short time I run a full (DirSync) sync
3.) Once the user is back synced from the OnPremises Active Directory I assigned him again an Office 365 license with an Exchange Online feature.
4.) After that I was able to perform the move via New-MoveRequest