Recently, my company got a new domain name, and I wanted to flush out the Outlook auto-completion entries with the old domain name.

In Windows Explorer: %APPDATA%\Microsoft\Outlook

delete all NK2 files

Close and re-open Outlook