Does the user get a bounce back email or error message when they try to send as that will often give a clue as to what is happening.
This can sometimes happen if the Outlook autocomplete cache in that users profile has become corrupt, so it's trying to use invalid information when completing the address. If that's always happening then the simplest option would be to clear their cache
so it can then start populating the information again with fresh and valid data. To do that go to File, Options, Mail, then in the Send messages section (near the bottom) you'll see a button for "Empty Auto-Complete List". Alternatively if it's just
happening for some addresses, when they find one which is doing this get them to start typing the address so the autocomplete displays the errant address, then on the right of the entry you'll see a X, click on that to delete that entry from the cache. Next
time the correct address is entered the details will be re-added.
The other time you might get this is where the mailbox has been moved from a different domain and those Outlook auto-complete entries were generated on the old system, though that's usually only an issue with internal addresses as Outlook / Exchange reference
internal mailboxes with the x500 address not the SMTP address, and since the x500 address is specific to the local domain it'll break if the domain / exchange setup is changed. In these instances you'll get a bounce message saying the address isn't valid and
if you mouse over the address you'll see it points to an x500/x400 address. Again the fix is to remove either the cache entirely or the individual entries as required.