@ return2sender:
Given your post is about a month old, I'm hoping you've resolved your issue. That said, based on the information you've posted - and if you haven't resolved the issue, it might pay for you to check your Active Directory Sites and Services configuration, as it sounds more like your Exchange server is having trouble determining it's site membership (which has nothing to do with MX records).
The quickest way of validating this is to run the following command from your Exchange server: gpresult.
If the line that lists the Site Name doesn't list a valid entry (typical values indicating a problem are either "N/A" or just blank space) then your real issue lies with your subnet to site associations.
A quick checklist would be:
1) Use NSLOOKUP to verify you can resolve the Exchange server's full DNS name;
2) Run the GPRESULT command to verify the site name;
3) If the site name is valid, then you can stop here as this isn't your issue;
4) Start Sites and Services (dssite.msc);
5) Expand the Subnets node and verify a subnet exists that encompasses your server's IP address;
6) Verify the subnet is associated with a valid site (I'm not sure how Exchange reacts if the site is either Default-First-Site [2003 domain controller] or blank [2008 domain controller] since we're not running Exchange 2007 yet).
Lastly, if you find that the site listed in the gpresult output isn't a valid production site, but the definitions in the Sites and Services MMC are valid, try restarting the NETLOGON service. For Server 2003, this prompts the server to reevaluate its site membership (I can't remember if this holds true for Server 2008). You could also try a "gpupdate /force" command, but from memory, this doesn't trigger a site reevaluation.
Cheers,
Lain