Hello again bwinzenz , I've just finished working with MS Support on this issue where the New-MailboxRestoreRequest fails as shown in my earlier comment. The case # was 21556719. They were very friendly and helpful (as there was another subtopic on the go as well). In the end, they could not confirm whether or the job should be considered successful or not in this situation. Instead the guidance was simply to avoid this situation altogether by not doing things that render a mailbox in both on-premises and EXO.
I've now done this process in 3 different customer tenants, plus my lab tenant and the outcome is 100% consistent, always fails with FailedOther and the error message about the mismatch of ExchangeGuid's. It seems like when the New-MailboxRestoreRequest Cmdlet was updated with the -Remote*** parameters, they didn't add logic to the actual working job to prevent this error.
I'm going to go now and submit the PR for the "How to recover" article so that it is at least documented based on the real world behavior of the process.
Thanks for the support earlier and also thanks Shaun Jennings as well.