The AutoComplete information of Outlook is stored inside a special file with .nk2 extension (on Outlook 2010 it's .dat extension). When Outlook AutoComplete is not working, it means that this .nk2 file is probably corrupted, and Outlook fails to read it.

You can fix the problem simply by deleting the .nk2 file, but you'll also lose the entire AutoComplete information accumulated until now.

Another alternative is to use NK2Edit utility to repair your NK2 file. NK2Edit utility allows you to load the entire nk2 file into memory, remove the corrupted records and fields, and then save it back into a valid NK2 file that can be used by Outlook.

Even if from some reason NK2Edit fails to repair the file, it also allows to build a completely new AutoComplete file according to the recipients emails stored in your Inbox.

Go to NK2Edit Web page