The auto complete cache in Outlook remembers all of the addresses that you have emailed and auto completes them when you enter an email address into the To: (or CC: or BCC:) field in Outlook. There are numerous fixes around on the web, but this one sorted the issue for me today on a stubborn Windows 7 machine with Outlook 2010 installed (with Google App Sync).

1. Close Outlook and go to %localappdata%\Microsoft\Outlook\ and rename RoamCache to old_RoamCache
2. Restart Outlook using the command line switch /cleanautocompletecache (“C:\Program Files\Microsoft Office\Office14\Outlook.exe” /cleanautocompletecache). This will rebuild the autocomplete cache.

These steps are based on an article at Spiceworks here: http://community.spiceworks.com/how_to/show/16443-repair-autocomplete-cache-in-outlook-2010. The second step was missing in the official Microsoft article.