In versions of Outlook previous to 2010, the history of e-mail addresses to which you sent e-mail were stored in a cache file. With Outlook 2010 these addresses are stored in an object in your mailbox (or .pst file). This will show you how to find and edit the auto-complete names list.
The object which stores your “Auto-Complete” addresses in Outlook 2010 is a folder in your mailbox/pst called “Suggested Contacts”. In the past, Outlook used a .NK2 file in “%appdata%\Microsoft\Outlook” to store these (and named the file after the associated mail profile). If you upgrade to Outlook 2010, the contents of the .NK2 file are pulled in to “Suggested Contacts”. To access it, select the “Folder List” view in Outlook (Ctrl + 6).
Now you simply look in Suggested Contacts for the entries that you want to change or delete.
To quickly and easily empty the contents of Suggested Contacts, you can also use the Outlook option to do so:
Select File > Options, then choose Mail, and scroll down to the Send Messages category. Select “Empty Auto-Complete List” to purge the contents of Suggested Contents.