I think you have DNS set up wrong. Having an MX point to an IP isn’t RFC complaint so will cause delivery problems. Review your DNS setting making sure you have an A record (host) pointing to your external IP. Something like mail.mydomain.com and then have your MX record point to mail.mydomain.com
Let us know
I agree with the MX record – it should point to an A record.
Other things to check: Are you sure that your server has port 25 publicly exposed via the mapped IP and protected by a firewall? You <b>DO</b> have a firewall right? Be sure that the server is also configured to relay e-mail from ONLY internal sources and does not permit relay from the outside world. Test that port 25 is open to the public by simply telnetting to port 25 on the public IP address of your mail server. This will quickly show you if the networking portion is working properly.