Microsoft introduced a new autocomplete feature in Outlook 2016, instead of showing only recently used addresses in autocomplete, it lists “Other Suggestions”. As with the previous autocomplete menu, recent addresses can be deleted by either selecting the entry then pressing Delete or using the X to the right of the name.
Since Other Suggestions entries don’t include the X, how do you delete them?
The easiest way, if Outlook cooperates, is to type enough of the name so that it moves up to the Recent People section, where it can be deleted.
If Outlook doesn’t cooperate, you’ll need to switch to Contacts and type all or part of the address into the Search Contacts field. On the Search ribbon, select All Contact Items (first button on the left of the Search ribbon).
The autocomplete entries are stored in a hidden folder called 'recipient cache', which is included in the All Contacts Items search. Autocomplete cache entries will only contain an email address; if you click the three dots in the contact card, the View Profile command, which shows you which folder the contact is in, is missing from the bottom of the menu (after Call). Select and delete the contact.
While we’re on the topic of the autocomplete cache entries showing up in instant search, I’ll mention that the DoNotIncludeNickNameCacheInSearch registry key breaks the new autocomplete dialog. It’s purpose is to limit the Search People results to actual contacts but with both Search People and autocomplete using the same control, it means the nickname cache is not included in autocomplete either.