This problem can be caused by importing Outlook autocomplete (the NK2 file) from one domain to another, when migrating domains or when there is corruption is autocomplete NK2. The outlook autocomplete address does not match the active directory address. The error message is accompanied by a bounce back message indicating that you cannot send E-mail to a particular person within your organization.
To correct this problem, follow these steps:
Open Outlook click New E-Mail. Begin typing the name of the person until the autocomplete displays their full name and e-mail address. Click on the x to the right of the person’s name to delete the e-mail address from the cache.
If you do not see the X, press the delete key on your keyboard to remove the autocomplete entry. Send the person a new E-Mail by typing in their full E-Mail address and the new remembered address will be the correct one.
You can also empty the auto complete cache which will make sure that you do not have any incorrectly remembered entries.
From Outlook, navigate to file –> options –> mail and click on empty autocomplete list from the send message section.
You can also empty the auto complete cache by closing Outlook then go to start –> run and enter the command outlook.exe /cleanautocompletecache