Error: MigrationPermanentException: Cannot find a recipient that has mailbox GUID

Error: MigrationPermanentException: Cannot find a recipient that has mailbox GUID

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-12345678

Then wait for replication to AzureAD and your mailbox move should go without a hitch.