I recently found that Apple Mail’s autocomplete was suggesting outdated email addresses. These email addresses were not in my Address Book, so I had no idea where Mail was getting them, or how to remove them. Luckily, I found the following solution in a forum post:

“Window” menu > “Previous Recipients”. This opens a list of all your previous recipients. Ever. Some are in your address book; some are not. [...] Just select one or all of them and hit “remove from list”.

Interesting. I never noticed that before.