What you mentioned here is bit confusing.
Why are your DNS entries pointing to two different hosts and that too not you server but ISP. (As i understood from the mail).
Your MX record should be pointing towards your server's "Public IP".
Also your published A record should be for the same server.
Also are you sure that you have reverse lookup entry of your server on Public DNS? just to be doubly sure go to http://network-tools.com
and in this check "Lookup" field for your server's "A" record and verify the result. If you get the result like the one mentioned below then your reverse entry is either not configured properly or maybe not configured at all, as was with
me.Hope this should be of some help.