In Outlook 2003, I have received and replied to email from the same
person at two different addresses: joe@foo.com and joe@bar.com. 
Outlook remembers and suggests both addresses when I start to type
"Joe" in a new message composition (see Advanced Email Options ->
"Suggest names while completing To, CC, and Bcc fields")

I want Outlook to forget joe@foo.com and only suggest joe@bar.com from now on.

How?!??!
:-)

Hint: Neither address appears in my Contacts list.  Outlook obviously
has some "hidden" contacts list which I can't find, where it puts
these "auto learned" addresses.

Thanks,
WS

Hi whitesorcerer,

Here you go. Briefly, when the pop-up list appears, use your up or
down arrow to select joe@foo.com and hit "delete". That should do it!

Top Tips for Outlook: [there's a long list of tips here]
"Delete names from the AutoComplete list   Select the unwanted name by
using the UP ARROW or DOWN ARROW key and then press DELETE."
http://office.microsoft.com/en-us/FX011052481033.aspx

Tip 099: What is Autoresolve and Autocomplete?
"Only Outlook 2002 and 2003 support Autocomplete. Also known as
suggest names, this is the feature that shows addresses of people
you?ve sent messages to previously and you can select matches as you
begin typing. You can?t seed the list with names from your address
book, the feature collects them when you send new messages or reply.
You can clear the autocomplete cache by deleting the *.NK2 file for
your profile or delete one address at a time by using the arrow key to
select it as you type and then Delete. Like autoresolve, you can turn
it on or off in Tools, Options, Email Options, Advanced Options."
http://www.outlook-tips.net/archives/2004/20040223.htm

I hope this helps. If you have any questions, please post a
clarification request *before* closing/rating my answer and I'll be
happy to reply. Please forgive me for taking so long in posting this.
I had it almost all ready to go when we received an important phone
call which tied up the line for some time.

Thank you,
hummer

Google Search Terms Used:

outlook 2003 autocomplete

Simple enough! Thanks!

Also, if you wanted to, you can delete the entire list of "learned"
email contacts. See instructions here:
http://www.123together.com/Support/How_To_Reset_The_Nickname_And_Automatic_Completion_Cache.htm