I understand that the rDNS records are under the control of my host. And I can see that I need to set them as I am getting emails from the mailer on my system that my mails are refused as spam because of the lack of a rDNS record. I can set them through the control panel. But what do you set them to?
My server is server.mydomain.com Do I just add a record for that, or can I add records for all my virtual servers at that particular IP?
Thanks.
In case anyone else finds this question. I did a lot of research and found that most mail servers, excepting AOL, will generally accept mail so long as the sender domain name, a fully qualified one, has an rDNS entry. So server.yourdomain.com where yourdomain is the domain name of the Virtualmin installation is acceptable, it does not have to be mail.yourdomain.com.
Please feel free to correct me if I my research led me to the wrong conclusion. I just want to learn so I can be better hostmaster.
Your research is correct. 
Since a mailserver usually is responsible for any number of domains in outgoing emails, and each IP can only have one reverse DNS record, it is not feasible to use “rDNS must match email domain” as a spam criterion.
The rDNS should, as you found out, exist though, and best not look like a dialup hostname, some spam filters don’t like that.