After trying to move a mailbox from Exchange Online to Exchange On-premises the above error occurred.
This happend because the mailbox was created online and not on-premises, and therefore the GUID wasn't synced to AzureAD and vice versa.
Luckily there is a simple fix:
In Exchange Online PowerShell:
Get-Mailbox alias | FL ExchangeGUID
In the On-Premises Exchange PowerShell:
Set-RemoteMailbox Alias -ExchangeGUID 12345678-1234-1234-12345678Then wait for replication to AzureAD and your mailbox move should go without a hitch.
