When you type in the To: field, you pull from your autocompletion cache, not
your Contacts Data. Remove the invalid entry 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.
To clear the entire cache, follow the instructions here:
http://support.microsoft.com/default.aspx?scid=kb;EN-US;Q287623

Signature
Russ Valentine
[MVP-Outlook]
>I am composing a message for a friend who has changed her address from
> MariaB@hotmail.com to MariaB@gmail.com. I have updated the address book.
[quoted text clipped - 14 lines]
>
> Did anybody else run into the same problem with Outlook XP?