Ideally, you would want to change your AD domain name to match your public domain name, but changing your AD domain name, once it has been configured, is impossible without completely wiping out your entire domain and starting over, so you really don't want to do that. Although it is not that common, it is possible to have Exchange use email addresses that do not match your local domain name. The only thing you have to be sure about is that your authoritative DNS server for your domain (wherever that is - probably at your ISP) has both an A (host) and an MX record in your zone that points to the correct IP address and name for your email server. Then, on your router or firewall, you have to set up port forwarding for the SMTP port (port 25) to forward all incoming packets to the correct local server.
In Exchange, you then use the Recipient Policies to configure the default naming convention for the email addresses.
Example: let's say your internal domain name is domainname.local, and your public domain name is company.com; your router IP address is 5.5.5.5 (remember - this is just for arguments sake ;-)); you want your public email server name to be mail.company.com; and your internal Exchange server's name is Exchange.domainname.local with an IP address of 10.0.0.1. Here's how you would do this:
1. On the authoritative server for your domain, create (or have your ISP create) a host (A) record and an MX record for mail.company.com at 5.5.5.5 (your router's public IP).
2. In your Exchange recipient policy, set up the SMTP address to use (mailnickname)@company.com for all of your users.
3. On your router, forward all incoming traffic for port 25 to 10.0.0.1 (the internal address of the Exchange.domainname.local server).
(continued below)