Autocompletion is not a robust or reliable feature. It frequently stops
working usually because Outlook loses its connection to its autocompletion
cache. This can happen for a number of reasons, most often because Outlook
is not exiting completely and thus not writing to the cache. Make sure you
run no add-ins or sync software that might hold Outlook open after you exit.
After you find and resolve the problem that is preventing Outlook from
exiting properly, you may need to create a new Outlook profile to get
autocompletion to work again. If you're lucky you'll be able to migrate your
old cache to the new profile following directions here:
http://www.ingressor.com/autocompletetips.htm