So.... usually... reverse DNS (where it is rejecting), has to do with the backwards DNS, pointing to your server, right?
In other words your server sets at 123.123.123.012. Your server's host name is : mail.hostname.com ... as an example, Your provider (lets say Level 3), would be required, to have put in a DNS reverse pointer, so that if anyone types NSLookup 123.123.123.012, that it resolves to mail.hostname.com. In order for that to happen, Level 3, in this case, has to establish that backwards PTR and name to resolve to.
When your server sends out email, then it has to be sure and send out over 123.123.123.012. If it is sending through a firewall, then you would need to make sure that the firewall, is indicated 123.123.123.012
Depending on what is going on your users, and the settings on your mail server, it could be that their I/P address (which may or may not be in your email - you can set this at the domain level) .. could be be the issue. Would be interesting to know if it is the same set of users every time.
As for IPV6, true ... I have disabled that.. but I am also ensuring that the above is true to.