Exchange and gmail

I have a 1 user that replies to another user on the network that uses gmail as the sending address. But when the 1st user replies to the gmail address, exchange resolves the second users email address on exchange and not the gmail address in the email. The cache has been cleared and the 2nd users contact info is removed from contacts in outlook 2003, leaving the gmail contact info only, but it still resolves the exchange address. I was thinking that because the name of the user is the same in both gmail and exchange, then outlook looks there first, don't know. What can be causing this. This is with only one person, and not anyone else that has or uses gmail and sends to the 1st user. Any ideas?