When an employee leaves the company, their account is removed, and then someone with the same name later joins or the original employee rejoins, Outlook auto-fill and or outlook contacts can cause emails to bounce.
Outlook auto-fill stores a reference to the actual exchange object (mailbox), not just the email address.
The new account created for the returning employee is a new mailbox, with the same name and email address as the old one which was removed. The old outlook auto-fill stored during the employee's first engagement points to a mailbox which has been removed and no longer exists. The old outlook auto-fill entry needs to be removed so outlook can search the address book and find the new mailbox.
Note the X at the right hand side next to the selected list entry in the screen shot above. Click the X to remove the entry from your Outlook auto complete.
Removing an auto complete entry may also be necessary for example when an ex-employee mailbox is removed and a group object is added with the ex-employee's address. The group will receive incoming email from the Internet with no problem, but internal mail can be disrupted because Outlook auto complete remembers the mailbox object (which no longer exists) and not the SMTP address.
Creating and using a new Outlook Profile also creates a new, blank auto-complete list. The old list remains in a hidden file on your computer. The old list can be removed or migrated to the new profile, although the process is cumbersome. See: How To Move AutoComplete Email Addresses In Outlook 2010/Outlook 2013.
Outlook 2016 for Windows introduced an easier way to completely clear the auto complete list, something a person might want to do for privacy reasons. Click File, Options, to enter the Outlook options dialog. Click Mail to view the mail related options. Scroll down to the Send Messages section. Click the Empty Auto-Complete List button. See screen shot below.