Hmmm....have you fired up the mmc and taken a look at your connectors? I don't think DNS is the issue - how is your server setup? SMTP? MX records point from the outside in, so even if you don't have that set up in DNS you should still be able to send mail out....do you have an internal domain with the same name as an external one, or anything else weird like that? More info please
/JD