Consider the following scenario:
Client computer running Windows 7 Pro (64 bit). Outlook 2010 (32bit) in an Exchange 2010 environment.
Outlook for this user will not remember auto-complete entries after restarting Outlook.
I've tried recreating his profile, uninstall/reinstalling Office, and even another computer - which indicates to me that this is a server/Exchange issue.
I've tried the suggestions found here: ice.microsoft.com/en-us/outlook-help/the-auto-complete-list-doesnt-remember-names-or-email-addresses-HA102534585.aspx
We've also done the "Empty auto-complete list" button in Outlook.
I couldn't say when this started happening exactly, but all users in Exchange are setup the same way and we haven't changed anything there. Everyone is working fine as far as I am aware.