This is generally due to Outlook's autocomplete/autoresolution settings adjusting the name and/or the display name of the email address.
You can try disabling the auto namecheck and autocomplete in your Outlook settings as sometimes simply doing this will resolve the issue.
Also, you can try Emptying the Auto-Complete List
It has also been noted that this can occur if the same information is found in multiple contacts. For example; if the fax number is the same in two contacts, it will report this error message. Other fields that can cause issues are the company name, phone number, etc. Outlook's integration API seems to take issue with multiple contacts with the same/matching data.
As a last resort, you can try deleting all instances of the contact causing the issue from Outlook. Be sure to check all address books the user has connected.
Alternately, consider not sending via Outlook and connecting to your e-mail provider via OAUTH directly.