AutoComplete Outlook Contacts Issues after adding external users to teams contact list

Dear all,

After adding external contacts (via email addresses) to the MS Teams contact list, these contacts' email addresses don't show up in the AutoComplete suggestions (or recent contacts) in Outlook. 

I have already tried to deleting the autodelete cache, which didn't work. 

Do you experience the same behaviour? Do you have any ideas how to fix the issue?