You posted no information on how you are selecting your recipient.
I would infer you are using your autocompletion cache. Are you?
Deleting Contacts does nothing to remove entries from your autocompletion
cache.
Remove individual addresses from the autocompletion cache by highlighting
the entry when presented in the suggested names list (use your arrow key to
migrate to the entry) and then hitting your Delete key before you tab out of
the field. If your autocomplete list contains only a single entry, use the
directions here:
http://support.microsoft.com/default.aspx?scid=kb;en-us;289975
If that article is unavailable, the gist of it is to send a message using a
name or address that will add another entry to that dropdown list. Then you
will have the ability to use the arrow key to select the name you want to
remove. This step is no longer necessary in Outlook 2003 and higher.

To clear the entire cache, follow the instructions here:
http://support.microsoft.com/default.aspx?scid=kb;EN-US;Q287623