I was doing a migration between Exchange 2013 and Office 365 in a Hybrid configuration when I recieved the above error message. Couldn’t quite figure out why until I stumbled accross a forum thread that pointed me in the right direction.
This is what you have to check out and remediate if you have this error:
The ExchangeGuids of on-premise users are different to the ExchangeGuids of the corresponding users in Office 365.
Update the online user’s ExchangeGuid to match the on-premise ExchangeGuid and start migration.
1. On the on-premise Exchange server:
Get-MailBox -Identity userID | Select ExchangeGuid
2. In an Office 365 PowerShell session:
Get-MailUser -Identity UserID | Select ExchangeGuid
If the results don’t match, copy the guid result from command 1 and then run the following command in the Office 365 PowerShell session:
Set-MailUser -Identity userID -ExchangeGuid “copied guid”
$Cred = Get-Credential
$s = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://ps.outlook.com/powershell -Credential $cred -Authentication Basic -AllowRedirection
$OnPremAdmin = Get-Credentials
New-MoveRequest -identity “UPN” -Remote -RemoteHostName “remote host ex OWA URL mail.domain.com” -RemoteCredential $OnPremAdmin -TargetDeliveryDomain domain.mail.onmicrosoft.com