Delete Remembered E-mail Addresses

When you type a recipient's name in the To box of a message, the AutoComplete feature's list of possible name resolutions contains names of contacts that you deleted already.

To work around this behavior, begin by typing the name and then, when the AutoComplete list appears, press the down arrow key if necessary.  Select the e-mail address which you no longer want to use and press the delete key to remove the entry from the cache.