This hint comes from MacFixIt: http://www.macfixit.com/article.php?story=20090429095454795

How To: Permanently remove addresses from Apple's Mail application

Apple's Mail application, similar to many modern e-mail clients, contains a function that remembers previous recipients. As more people change e-mail addresses for work, because of server changes, a hacked account, being spammed, or just to try out a new e-mail service, it gets harder to maintain your contact list. While many users change or delete e-mail addresses in Address Book, they are finding the old addresses keep appearing in the auto-filled To: field in new messages.

Issue

A colleague recently let me know that they changed their e-mail address. So I went into Address Book and changed the info. But whenever I create a new email and start to type in the person’s name, Mail wants to use the old address.

Is this a bug or am I overlooking something? Bottom line: How do I totally get rid of the old email address?

Solution

While updating your contact’s information in Address Book is definitely the first step; the second step involves editing your Previous Recipients list in Mail. To do this:
  1. Open Mail.
  2. From the Mail menu bar select Window->Previous Recipients
  3. You can now select each address you no longer need to show up and click "Remove From List" (Hint: Use Command-Click to multiselect addresses.)

    You may sort the "Previous Recipients" list by name, e-mail address, or last used by clicking on the column header (twice to switch between ascending and descending).