check the MX entries from a seperate internet connection.
from a command prompt, type in nslookup -type=MX {domain name}
next thing to try would be to telnet to your e-mail server on port 25 from the internet.
(don't use the IP address, use the hostname that is returned from your nslookup.)
If you've got connectivity, you will get a reply and you can type in helo and get an answer.
If you get nothing, you've found your problem.