What you want to do is use nslookup on the Exchange server. At a command prompt type nslookup then enter.

At the >> prompt type 'set type=mx' (without the quotes) and hit enter.
then type the domain you are trying to send the email to and hit enter.

This will show you the mx records (Mail Exchange) for the domain as your exchange server sees them. If it doesn't find any then there is your issue. It is with your DNS server. If you do get entries but not sure if they are correct you can repeat the procedure above except the first command you should run inside nslookup is 'server 4.2.2.2'. That will get dns records from a root server instead of your local dns. If the mx records match from what you had previously then your dns is fine, if not then you have found your problem.

As far as the pings go, you might have a firewall at work that blocks ICMP traffic. Instead of pinging try to telnet directly to their mailserver. Use 'telnet domainname.com 25' at a command prompt to telnet to port 25 on their server.

Thanks for the reply. I did what you said and it looks like my DNS is to blame because it is displaying a different nameserver than the root server is.

But how do I fix that? I've tried searching the Internet for the solution, but can't seem to find anything. I haven't had any training with Exchange 2K3 and only a little with DNS so far. Thanks again.

Isnt that due to NAT?

e.g

my ISP assigns me the public ip 62.1.2.3 (i just made that up). and if I were to have a webserver with 2 network cards (one public (62.1.2.3) and another local (192.168.1.1) and i were to ping it from the local etwork i would get the IP 192.168.1.1 whereas if i were to ping its full domain name (or ping it from outside the lan) i would get 62.1.2.3

and i have my NAT capable router to forward all mail requests to a mailserver on my LAN (lets say, 192.168.1.2) therefore if i were to ping 62.1.2.3: [whatever port it is for pop] i would actually be pinging 192.168.1.2

does that make any sense?

nolanjb is trying to ping a remote mailserver. The dns entries should be the same. The dns service on his network will hold static and dynamic entries for computers on the lan, and cache entries for external servers.

nolanjb. What you need to do is check the network configuration of the Exchange server to see what DNS server it is using. If it is one of your local servers then log on to it and check your dns settings. Make sure the remote computer doesn't have a static entry in your dns. Once you have verified that open a command prompt on your dns server and type:

ipconfig /flushdns

That will flush the remote dns entries out of the cache and will contact another server for the entry the next time you do a lookup. It could be that your service provider still has an old entry cached in their dns which means it could take up to 3 days for it to update.

but NAT will not allow incoming ICMP and will masquerade the lookups. isnt that supposed to be true and that's what jbennet pointed out

I think you need to understand what the question was and how NAT and statefull firewalls work. ICMP traffic generated externally will not enter a typical statefull firewall. But he was generating the ping requests internally. When he does that a translation table entry is created and an entry in a connection table letting the firewall know that traffic was generated internally to an external host and to expect and allow the traffic to return. Most home routers allow this by default, but devices for businesses like the Cisco PIX and ASA do not. You have to specifically allow ICMP traffic.

As for "masquerading the lookups", that is not how NAT works. What would it masquerade to? If you are behind a statefull firewall using NAT and have a private IP, when you do a ping or nslookup to an external host you will see the IP of the external host. Otherwise the packets will not be routed. What address did you think it would show?

If you are behind a firewall right now then try it. Ping an external site like google.com and see what IP address it returns. It's the actual external IP.

Thanks spenser, I will do that and wait a few days and see what happens.

That didn't work. However I did solve the problem. I called my service provider and it turns out it was their problem. Thanks for everyone's help.