Bei Outlook 2010 kann es vorkommen, dass die AutoVervollständigen Liste nach einem Neustart nicht gespeichert wird.
Einfaches Problem, einfach Lösung.

Outlook braucht einfach nur mit einer Option gestartet werden.

Outlook.exe /CleanAutoCompleteCache