@Dashrender said:
Well the name.nk2 file itself might be retired, but the autocomplete listings are still there and are not fixed when someone changes addresses.
I had this problem last year in Outlook 2013
They only way to fix that would be to clear the auto complete list. That's solely based on the most common emailed addresses. It's per user and doesn't store on exchange in anyway (and isn't sync with OWA, OWA uses it's own list)