Hybrid EXO - The execution of cmdlet Set-SyncMailUser failed

Hello

So we have following situation:

Hybrid environment

Staff member with migrated (remote) mailbox leaves the company

license is removed

user is moved into a non-sync OU and O365 mailbox is moved into deleted users

after the grace period, mailbox is deleted

same users comes back in the company few months later (after the grace period of the mailbox) and the same AD account is re-enabled and re-synced with O365

In the on-prem exchange console the same mailbox is showing as : Remote O365 mailbox

but in EXO is nothing, no mailbox

assigning license returns error: Exchange: The execution of cmdlet Set-SyncMailUser failed..; Exchange: An unknown error has occurred. Refer to correlation ID

and if try to perform new-moverequest also returns error:

The operation couldn't be performed because object 'returning-staff@abc.xyz' couldn't be found on '........PROD.OUTLOOK.COM'.

I checked the Error field via MSOL, but showing nothing, literally empty space

Also checked the "msExchHomeServerName" its all clear

Not sure what else to look for/change