Why do users depend on silly, flimsy and unreliable features such as email auto completion in Outlook. The auto completion works by cashing the typed email addresses in NK2 and NICK files. By design these files are temporary. They are not backed up or archived and Outlook can delete them on a whim without a working. Relying on a cashing scheme rather than on the built in address book is usually not the best idea.
Especially since the cache files can get corrupted. I’m not sure how Outlook maintains this index, but my wild guess is that they use a hash file. The file grows very slowly so I’m betting that that they simply maintain the hash in the memory, and dump it into the file once Outlook shuts down. If you get only a partial dump, Outlook will try to pick up the pieces and recreate the cache. If your file gets totally fuxed, it will nuke it and start from scratch.
I think the problem happens when you fall right in between a minor write error, and a grand clusterfuck. You get outlook constantly trying to recreate a file that is broken enough not to read properly on the next startup, but not enough to warrant a complete wipe. Manually deleting the NK2 file seems to solve this issue.