Outlook Auto-Complete does not work or stops working. This happens for 3 possible reasons.
1. When you exit Outlook, the program closes but the program is still running if you look into Task Manager.
2. User does not have ownership of the "Suggested Contacts" list.
3. The "Nickname" file is corrupted.

To fix this do the following.
1. Open Outlook and click on File then Options. Click on Add-ins and then click Go next to Com add-ins and uncheck the following add-ins. Uncheck Mobile Me and Bonjour.
2. Open Outlook and click Contacts. Right click on Suggested Contacts and click properties. Make sure the User is the owner with full rights. Change Default to none if set to owner.
3. Open Outlook and click on File then Options. Click on Mail and scroll down to Send Messages. Click Empty Auto-Complete List and click OK.

Now the Auto-complete list will start to repopulate as they send emails.