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 mx01.emig.gmx.net[213.165.67.97] refused to talk to me: 554-gmx.net (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 mydomain.com - 123.123.123.123 www.mydomain.com - 123.123.123.123

CNAME
nothing set

MX Records
mydomain.com 10 mx.mydomain.com Active
mydomain.com 20 mx2.mydomain.com Active
mydomain.com 30 mail.mydomain.com Active

NS Records
mydomain.com s1.customns.com (s1 to s4)

(There are also TXT, SRV and SOA Records)

In Virtualmin I see:
SPF - Sender Permitted From v=spf1 a mx a:mydomain.com ip4:123.123.123.123 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
vps.mydomain.com - 123.123.123.123

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:

yourdomain.com. IN TXT "v=spf1 a mx a:yourdomain.com ip4:123.123.123.123 ?all"