To remove email address of sent messages from Mail
In Mail, click on the Window menu then Previous Recipients.

To locate people not in your address book, click on the empty column header all the way to the left (to the left of Name). The ones that are in your address book have an icon in that column.

Select the recipient you want to delete and click Remove from List in the lower-left corner.

Screenshots are available on this University of Wisconsin page.