This is actually down to Exchange’s Suggested Contacts, I think.

 

If you open up Contacts, choose the Exchange account, you can search and remove the offending contact there. the actual list of “Suggested Contacts” appeared empty to me, but searching overall did return the contact in question, and removing it has finally removed it from the autocomplete list in Apple Mail.