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.