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.