RecipientNotFoundPermanentException when migrating a mailbox to Exchange Online

The other when migrating a mailbox from an on-prem Exchange 2013 environment to Exchange Online, I was faced with a RecipientNotFoundPermanentException error with the message “Error: Cannot find a recipient that has mailbox GUID '39c970e4-4869-47ee-b9af-f6fd6264ee0a'.”

 

These were the details for the mail user in Exchange Online (notice the ExchangeGuid attribute):

 And these were the details for the mailbox on-premises:

  

As you can see, the ExchangeGUID was the same! And where was that '39c970e4-4869-47ee-b9af-f6fd6264ee0a' GUID coming from?!

After much troubleshooting, I ended up logging a support ticket with Microsoft. According to the engineer, “this issue is caused due to multiple mailbox shards”. Unfortunately, he wouldn’t go into details as apparently it is all secret stuff... But he ran some diagnostics to resolve the issue, and after a few minutes all was well with the world again!