If you control the DNS for the hosted domains, there are a couple of things you can do.
First, make sure that your virtual server is listed as the primary MX record for each domain. That means it will be accepting inbound mail for the domain, which I presume is what you want to do.
Second, add an "SPF" record to the domain's DNS that looks like this:
That tells remote mail servers that honor SPF records that your hosted server is the valid outbound SMTP sender for the domain. If other servers are valid as well, just add additional "a:hostname" entries separated by spaces.
@ IN TXT "v=spf1 a:virtualhost123.myhostingprovider.com ~all"
It sounds like forward and reverse DNS are set properly which is the other common issue with sending mail. I don't reject inbound mail from hosts whose reverse DNS doesn't match their claimed hostnames, but I give those machines extra points in SpamAssassin.