Delete Remembered E-mail Addresses from Outlook

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.  Highlight the e-mail address which you no longer want to use and press the delete key to remove the entry from the cache.

To get the proper address remembered now you should use Outlook to Compose a message. In the Compose message window, press the To: button and look the person up in the Global Address List. Send that message and you'll have a good address stored now.