Mail.app: Clear Address Auto-Fill Cache
See the menu Window -&gt; Previous Recipients - you can select all and delete or be more selective.

Once that's done you may also want to prune your address book or disable mail from auto-filling from there as desired.