A quick tip I just found after too much digging in Google:
Deleting an email address from Mail.app’s autocomplete list can easily be done from the Window, Previous Recipients menu. Nearly every search for autocomplete adjustments says this.
But I wanted to do the opposite: add addresses to it, since I rely so heavily on autocomplete when composing mail, and my new clean installation started with an empty list. I still can’t find any way to bulk-add — I’d love to just autocomplete every recipient’s address from every message in my Inbox or folders.
But I did find the autocomplete file’s location so I could migrate it over from my old computer’s disk:
I quit Mail, copied that to the new computer (mine was 954 KB!), overwriting the stock one (only 49 KB), and relaunched Mail. All of my old autocomplete entries were back with no apparent side effects.