Double Checking MX/Reverse iP Problem/Solution

[LyleS]

I would like to double check with someone that I am doing the correct thing.

I have a server with lots of domains... we'll say x.com, y.com, z.com and each has mail.x.com, mail.y.com, mail.z.com (respectively) setup automatically for them. All domains are hosted on a single IP 1.2.3.4 and the "main" domain name for the (PLESK) server is mail.server.com

1.2.3.4/mail.server.com does have everything setup correctly, domains resolve correctly, reverse DNS on the IP resolves to mail.server.com, all dnsstuff.com and mxtoolbox.com stuff says the world is great and I can even send to who ever in the world I please.

I am seeing reports of clients of my other PLESK hosted domains getting their email occasionally rejected on some of the bigger ISPs (AOL, bellsouth, craigslist, TimeWarner, etc) due to (mainly!) being that their reverse DNS record for the IP of the PLESK server does not match the MX record for that particular domain. Which I understand (I think!).

Wouldn't the solution be to simply change the MX records for x.com, y.com, z.com to point to mail.server.com, instead?

Not getting into SPF records quite yet, but I was thinking this could solve most of the issues. Or I could be completely wrong

Thanks!