There are some possible problems regarding mail, thanks to spammers.
You properly need to set up a MX record to your IP and open to your mail server from the net. The receiving mail server will want to confirm your server.
My ISP sets all there IPs on a blacklist. I then have to go to the blacklist and get my IP of it. They do it once en a while.
Most mail server greylist mails. So Postcast need to be able to resend.
Maybe you can set up an accept of your mail server by white listing it on you mail account?
And so on.
Do you get an answer mail, that tells why you are rejected?