emails being rejected by remote server - invalid DNS PTR resource record

I am moving to a new VPS with more RAM (1Gb on CentOS 6.6 32bit). And so far most things work fine with the first domain moved. I can receive mails - but when I send a mail it gets stuck in the postfix mail queue:

host[] refused to talk to me: (mxgmx112) Nemesis ESMTP Service not available 554-No SMTP service 554 invalid DNS PTR resource record

Is that related to a wrong MX server setup? My details similar to:

A Record - -

nothing set

MX Records 10 Active 20 Active 30 Active

NS Records (s1 to s4)

(There are also TXT, SRV and SOA Records)

In Virtualmin I see:
SPF - Sender Permitted From v=spf1 a mx ip4: ip6:2888:180:1:b2::7896 ip …

But I also see:
Warning - errors were found in this domain’s DNS records : This domain has email enabled, but none of the MX records point to it. Either the MX records should be corrected, or the email feature disabled if mail is hosted externally.

I hope somebody can point me in the right direction to fix that.

Update, I set:

A Record -

And put that into the RDNS of my VPS. Mails go out now.

I just wonder if that is the correct way?

You have to set a TXT record: IN TXT "v=spf1 a mx ip4: ?all"