Update: Also check out this related post on dealing with certificate errors when users access Exchange from both the company's internal network as well as from the Internet:

/en-us/community/blogs/Lists/Posts/ViewPost.aspx?ID=4

I had just installed and configured (at least I thought I did :) ) Exchange 2007. I sent a couple of test messages through from one internal account to another. Things seemed to be working well. But, when I tried to send a message to an external (Internet) address or receive a message, nothing happened. I did not get any obvious errors but the messages just did not get through.

It turns out that you must do some additional configuration on Exchange 2007 in order for it to allow inbound or outbound traffic from outside of its domain; that includes Internet messages. In order for Exchange 2007 to be able to send and receive Internet mail:

1. Enter the Internet FQDN as an accepted domain
   
2. Enter the Internet FQDN as an address policy ahead of the default policy for the local FQDN. This gives users two addresses: user@localFQDN and user@InternetFQDN and sets user@InternetFQDN as the default SMTP address. To test this, send an email from a user and check the user's from address. It should be user@InternetFQDN , not user@localFQDN. For example, if user jsmith in the mycompany.local domain sends the email, the from address should be jsmith@mycompany.com not jsmith@mycompany.local.
   
3. Allow anonymous permissions on the default Receive connector. This allows people from the Internet to send email to the Exchange organization. If this is not done, emails from outside bounce with a message saying the sender was not authenticated. To test this, send an email from an external account, like Hotmail, to a user within the Exchange organization.
   
4. Create a Send connector with the destination domain specified as "*". This allows the Exchange organization to send email to all domains. If this is not done, email sent outside the organization will be held by the server. The sending users will not receive any notice that their emails have not gone through. To test this, send an email to an external account, like Hotmail, from a user within the Exchange organization.