Try these steps.
First, reset the auto-cache following this method even if you already have:
1.Close Outlook, go to Start > Run > type "outlook.exe /cleanautocompletecache" and hit Enter. On Outlook startup, choose your Exchange profile. It will be loaded without cached entries.
Source
Then, follow these steps to fix the emails that don't work:
Source

The culprit I believe is the "mailto:" tags that are part of your contact's addresses. Clearing the autocomplete and making sure they are set to smtp instead of mailto should resolve this for any contacts you have or things you type not immediately failing. If this doesn't work we may have to come at it from another angle.