When the autocomplete cache won't retain addresses across a reboot or a
restart of Outlook, then either Outlook isn't closing properly when you close
it or the connection between the cache and the mail profile is damaged. A new
profile should repair the latter. If the problem is the former, you'll have
to track down why. See http://www.howto-outlook.com/faq/outlookdoesntclose.htm