Many of my friends and ex-colleagues are aware that I once disgraced myself by sending a humorous (and genuine I might add - it was NOT a photoshop-job) picture to my entire company as the result of an AutoComplete trauma; "XYZ Developers" turned out as "XYZ Global". (I'll post the picture at a later date when I'm back at home.)
I took a couple of things away from this experience:
1. Beware AutoComplete.
2. When you recall a message, the message isn't recalled silently, rather Exchange sends a message to the intended recipient asking if they agree to have the message recalled, which is a bit like adding a "READ ME" notice in size 48 font (bold) to the original message.
I survived, but I've been wary of AutoComplete ever since, especially as it also has a habit of storing invalid email addresses. It essentially scoops up any old cr*p that you type in the Tp/cc/bcc box and adds it to the list.
Imagine my delight, therefore, when I hit delete whilst highlighting an invalid old email address in the a/c list, whereupon it vanished. I did a quick google, and it turns out that this is a supported behaviour (see KB289975); however this can't be done with single entries.
A more radical suggestion is just to blitz the entire a/c list (KB287623) - take your pick.