This may be an Outlook Cache issue:

Try to clear your NK2 files.

or

Start typing recipient (problem email user) in the "To" field and when Outlook attempts to autocomplete, highlight the entry and press Delete.