Many people don’t realise that the Mail program on a Mac stores all your sent email addresses. Clicking on ‘Window’ in the menu at the top of your screen and then clicking on the menu item ‘previous recipients’ can access these.
When you send an email, the addresses that appear when you start typing come from both your contacts stored in the Contacts App and also from this previous recipients list. So, to remove any unwanted email addresses, you need make sure you check in both places.