I use Apple Mail.app daily, and I've noticed that sometimes it auto-completes email addresses that it shouldn't know about.
For example, if I'm on mac "one", Mail.app knows about email addresses that I've encountered on other machines that I use, but that I'm positive have never "passed through" mac "one". I've checked the contacts in Contacts.app (local and iCloud), as well as all the local mail boxes managed by Mail.app.
On other machines, these email addresses have been seen by other instances of Mail.app, even though their configurations are independent from mac "one".
The only thing that links the macs is my iCloud account, but "Mail sync" is disabled.
I am trying to understand how Mail.app builds its list of known contacts, where it's stored on disk, and how it syncs them between macs.