Outlook never autocomplete a specific address

Question

Hello,
I am stuck with a user for who Outlook never autocomplete a specific address, even if:

• The user already sent email to it in the past
• The user had a contact, that we removed, and even cleared with MFCMAPI (Recipient Cache etc), and re-created
• Profile re-created multiple times with all Outlook %localappdata% files deleted

User has the contact:
Name: A .... Br ....
Email: ******@....hant.com
![275662-abr-contacnthidden.png][1]
User already wrote in the past with first autocomplete working ONLY when doing CTRL-K:

Outlook never offers autocomplete for that contact address ******@....hant.com, it only offers for other addresses that contact has / had (one in @Israel Bautista .ch and another one ending with @....up.ch):

That user used to have a cached address we found using Exchange EWS API, that I completely cleared using MFCMAPI:

As you can see it used to have also the second address that autocomplete succesfuly in the previous screenshot.
Contact is well removed completely, including cache address, and only remaining new contact has the correct address:

Note that this domain ...hant.com was previously in our O365 Tenant, and all users were migrated to another tenant.
That user on our side with issues had all those people as Contacts, and clearly Cache was a problem. We fixed successfully 3 of his contacts by either deleting the contact and / or make sure any cached autocomplete was removed, after what autocomplete started to work again. But this one is just impossible to fix.
Autocomplete work on WebMail (O365), just not in Outlook.
I'm out of ideas and O365 support is just useless repeating loop of same useless actions (I have 6 years XP in Exchange and I know when there is a clear deep bug that basic level 1 support won't do anything).
If anyone has further ideas I am open to.
Cheers
[1]: /api/attachments/275662-abr-contacnthidden.png?platform=QnA