If deleting the Auto-Complete entries individually isn't working, then you'll probably need to clear the entire cache. I've seen this behavior in various versions of Outlook, and clearing the entire cache was the only thing that would fix it.

To clear the cache in Outlook 2010:

1. Open Files > Options.
2. Click on Mail.
3. Scroll down to the Send Messages section, and click the button labeled "Empty Auto-Complete List".
4. Click Yes on the confirmation.

You may also want to check and make sure that the old email address that's coming up isn't listed in any of your contact lists.

Hope this helps.

-SW