Shaun Jennings the on-premises original mailbox is soft-deleted (the ExchangeGuid in the error message is that mailbox's). The original user in on-premises is now a RemoteUserMailbox and its ExchangeGuid has been set to match that of the EXO-based mailbox. I'm doing New-MailboxRestoreRequest in EXO v2 PS like this:
New-MailboxRestoreRequest `
- Name <PSmtp> `
- BatchName "Migration via Restore" `
- RemoteCredential $Credential `
- RemoteHostName <on-premises EWS/MRS proxy FQDN> `
- RemoteDatabaseGuid <on-premises MDB Guid> `
- RemoteRestoreType DisconnectedMailbox `
- SourceStoreMailbox <ExchangeGuid of soft-deleted on-premises MBX> `
- TargetMailbox <ExchangeGuid of EXO MBX> [ENTER]
It seems like I'm following the instructions in the "How to recover when a mailbox...." article perfectly, with the exception that for step 7, I'm also including the Name and BatchName parameters. Otherwise I've executed everything exactly as instructed. It's really strange too whereas I can see in the report that the on-premises mailbox is connected to and its items are successfully copied to the cloud mailbox.
Going back to your question about the main AD account - it was never deleted from on-premises AD, nor from Azure AD, it was mailbox-enabled in EXO before EXO was aware that there was already a mailbox for it in on-premises.