DNS for Separate Incoming/Outgoing Relays

We currently have two separate email relays and twenty different email domains. One relay is for incoming email, one for outgoing. We have at least one company who is rejecting our mail because they say we have no reverse DNS entry. Their tech department said this is a standard sendmail check to block spam and anyone using sendmail will also block our email. The MX record for these domains point to our incoming email relay, not the outgoing. What DNS change would you recommend so sendmail won’t reject our messages?