How can I remove email addresses from Mail's autocomplete?
I've had this same concern and from what I understand Apple does not provide a method to accomplish this cleanup. There are many threads in Apple Support discussion board and they always end suggesting to email Apple the request for this ability.

However, if you own a PC, this gem popped up:

Can't delete Unwanted Email addresses, Auto-fill in saves them all !