In a medium to large companies, there is lots of change continually happening in Exchange Servers and Active Directory, like new mailboxes, migrations, Name changes, deletions, etc., The reason I bring this up is the Outlook Address Book. Is your Outlook Address Book (Exchange GAL) is current? Is your auto completion cache valid anymore?
In my scenario, Users get migrated from merged company and they get new mailbox and email address. While we lived in-between pre-migration and migration, There was few calls to the help desk from users saying they are getting bounced mails (Non-Delivarable Mails) sent to legitimate internal users.
It turn out to be Outlook auto completion cache had old expired email address which doesn’t exist anymore. When we convert a contact to a "Mailbox-enabled" user accounts, they get brand new X400 address. Outlook "Offline Address Book" and auto completion cache didn’t get updated to the new X400 address, thus all the NDRs.
Here is how I resolved it.
1. Add the X500 address as an additional E-mail address for the migrated users.
You can find out X500 address of the expired account is two ways.
a) Tell the user to type the name of the ‘troubled’ users name in "To" box in Outlook Compose window. Right click on the resolved user account and open the properties. It will show the exact X500 address you want.
b) Track the bounced message in Exchange System Manager or Exchange Management Console. Tracking result will display the X500 address of the expired account instead of display name.
2. Delete the Outlook Address Cache. See the link below.
How to reset the nickname and the automatic completion caches in Outlook
3. Delete any Outlook Contacts for the troubled users and re-add it from GAL
4. Just in case, Manually download the Offline Address Book in Outlook. To do this,
a) Open Outlook
b) Click Tools –> Send/Receive –> Download Address Book
c) Leave the default settings and click OK.