I have a user on Exchange 2007 server, tried adding an additional SMTP address to their mailbox. I e-mail it just fine internally. Externally like from Gmail, I get an error back from the mail server and the final code of "550 5.1.1 Recipient address rejected: User unknown".
Does it take time to sync the new SMTP address?
I tried it with a mailbox on Exchange 2010 and it worked instantly.