Outlook remembers both wanted and unwanted addresses.
Deleting Unwanted Email Address from Outlook’s Cache
Outlook remembers up to 1000 email addresses you’ve used in the past, even if you have never stored them as Contacts. There are pros and cons to this behavior. One benefit is that you can easily retrieve email addresses you have used just by typing the first few letters. A drawback is that as you update your contacts, the AutoComplete name cache file remains static. So even though you have changed a contact’s email address several times in the course of the year, the one Outlook suggests when you start typing the person’s name in the To field will be the wrong one. These phantom e-mail addresses can cause an email to bounce back especially if you had mistyped the email address the first time. Furthermore, there is no way to edit the file where these names are stored since it isn’t written in plain text. Nevertheless, you can delete entries from the cache one at a time when necessary. To accomplish this:
1. Click the New button to open a new message.
2. Type the first three character of the cached name into the To field to trigger the AutoComplete feature.
3. Press the Down Arrow key on your keyboard to highlight the name or email address you wanted to delete.
4. Press Delete on your keyboard to remove it.
For more information check out http://support.microsoft.com/?kbid=287623 (see below)
(Here’s the info from that link page.)
To reset the whole Outlook nickname cache for Outlook 2010, use one of the following methods:
Open Outlook 2010.
On the Filetab, click Options. See image
Click the Mail tab. See image
Under Send Messages, click Empty Auto-Complete List.
Outlook will generate a new nickname cache.