When I try to send an email to someone I know works here, it bounces back with an error.
Background information
If the employee left and has returned, then the Outlook entry "looks" the same, but internally the UID is different, therefore the original UID is no longer valid.
Solution
To resolve this issue you should remove the old entry that is auto filled in Outlook and find the name again in the address book. After sending a successfull email once, there should be no further issues.
Open a new email in Outlook
Start typing the name of the employee
When Outlook shows the options, click on the little "x" beside to the name to delete it
Now search for the name again by typing the first name and then pressing Ctrl + K