Yeah, two basic troubleshooting tips.
1. Do as was listed above, connect FROM THE OUTSIDE WORLD to your mail server on port 25 and try and send yourself a message manually.
2. From a machine on the outside world, get to a command prompt and use:
example.com. (Use the domain after @ in the email address)
mail.example.com. (lookup any domain name redirects you get)
and see if it returns the right IP address.
If #2 fails, it's a DNS problem. If #1 fails with a timeout, it's likely a firewall issue, if #1 fails with connection refused, it's your server's mail accepting software's listening configuration. If #1 fails with a valid connection, but a refusal to deliver, your mail software may not be configured correctly to accept mail for that domain.