A year or two ago a friend switched email addresses and told me to stop using the old one. I did what any of us might, which is to go to the Contacts app on my Mac and remove the old address, in favour of the new one. This should then change my iCloud address book too. It did, and it appeared worked fine.
Fast forward to today when the same friend complained I was still using the old email address.
The reason is that the Mail app on a Mac uses both the address book and its own, private list of recent addresses. My friend’s old address was in that list and Mail autofilled it when I typed his name. To view this list you can click Window > Previous Recipients. The best policy is to search by name, select the errant address, and click the remove from list button.
Alternatively, you could select all the items in the list and remove them all, relying only on your contacts list/iCloud address book.