The auto-complete data is stored directly on the users mailbox database (since exchange 2010).
I had the same problem with a single mailbox. I ended up having to migrate the entire user to a new mailbox (deleted and restored). However this is only on rare occasions.
Few things you can do that usually fix this.
- Move the effected users mailbox to different databases (this causes exchange to check mailbox integrity insisted of waiting).
- Have the user login to there account via Outlook. In outlook go to File --> Options --> Send Messages --> Empty Auto-Complete List. After you do that wait 2 minute to make sure that outlook sync that change to exchange.
Make sure that works by restarting the outlook client and seeing if it fixed the problem.
If that didn't work your best bet is to initiate a complete mailbox export request via exchange powershell and delete the account. Recreate immediately and re-import data you
Note: When you do this, it will cause everyone's auto-complete for that user you recreated to not work until they re-add the user from the address book or delete that user from auto-complete (price you pay).