Did you try using the arrow down key, and then hitting the delete key on the auto-complete entry? I just tried it, and it deleted the email when I tested, and didn't come back when I opened a new email.

If you take a look at this registry key, vista mail seems to write to it every time a mail is sent out.

HKEY_CURRENT_USER\Software\Microsoft\Windows Mail\Recently Used Addresses

Close down vista mail entirely, remove all the entries on the right-hand pane other than the (default) one, and then re-open vista mail. (mine has one called "a" and another called "MRUList".

Let me know if that works for you.

Glad it worked!