Odds are good that your Internet DNS is being hosted by a third party, and that's where you'll need to make the change. Run the following command against an Internet DNS server and look at the results:
nslookup -type=SOA your-domain-name.com
(If you're using "your-domain-name.com" as your Active Directory domain name then run this at home against your ISP... and shame on you for using a real-world Internet domain name as an Active Directory domain name.)
You're going to get back the Start of Authority record for your DNS zone. In the "primary name server" and "responsible mail addr" lines you'll probably get some hints about who is hosting your DNS. Odds are good it's your domain registrar (Network Solutions, GoDaddy, etc).
Your DNS hosting provider will have a DNS "control panel" that you can use to specify your MX records, etc. That's where you'll need to be making these changes.
As an Exchange admin (and a sysadmin in general) it would do you well to learn about how DNS (and the interaction between DNS and SMTP via MX records) works. You should know, right off the top of your head, who is hosting your Internet DNS for your corporate domain name. It's the kind of thing that's sort of important. >smile<
(An appreciation for using DNS is something that I wish more sysadmins would gain. I think I'll scream if I run into one more company distributing VPN connection 'profiles' that name an IP address as the VPN gateway instead of a DNS name... GRRR!)
