When you send a message in Mail, the addresses to which you sent the message are stored in a database called the "Previous Recipients" list, which serves a number of purposes, including facilitating address entry for future emails as well as being available for Mail rules such as the junk filter.
Periodically, there may be issues with the previous recipients list, where either the list will not clear, or you may have lost the list and would like to restore it from a backup (as was the case with a commenter on the article I).
Despite the fact that Mail is the predominant application that uses the "Previous Recipients" list, it is not stored in the Mail application's resources (ie, along with the mailboxes and RSS feeds) in your Library folder. Instead, it is in the same location as your Address Book database for all your local contacts. The file is called "MailRecents-v4.abcdmr" and is located in the /username/Library/Application Support/AddressBook/ folder.
If you are unable to remove or add previous recipients, try deleting this file and relaunching Mail as you would do with a faulty preferences file, which should recreate it and hopefully clear the problem. If you would like to restore from a known backup, go to this location and invoke Time Machine (or otherwise locate your backed up file), and restore your backup to this folder, overwriting the current file.