How do I stop email addresses from spam autocompleting in Apple Mail?
One possible option is to delete the file that stores all that data. That file is stored on:

/Users/YOUR_USERNAME/Library/Application Support/AddressBook/


There is a file called:  MailRecents-v4.abcdmr

Seems like that file stores all the autocomplete address.

If you delete that file you will lose all others previous recipents address. So I'll follow the following steps:


In Mail.app: Menu Window > Previous Recipents. There copy all address that you don't have stored in your contacts and you want to keep
Close Mail.app
Backup MailRecents-v4.abcdmr file by copying it to desktop (for example)
Delete all files called MailRecents-v4.abcdmr stored on /Users/YOUR_USERNAME/Library/Application Support/AddressBook/ folder. You will see another MailRecents-v4.abcdmr-* files. They store other info of the autocomplete address.
Open Mail.app and try to create an email.


PS: If something goes wrong opening the Mail.app on the step 5., restore the backup files that you copy to the desktop.