Sent mail blocked because of Domain/IP Reverse lookup conflict.

Sent mail blocked because of Domain/IP Reverse lookup conflict.

Whenever we send an email through Zoho to one particular email server, all of our emails get blocked as spam because the sending domain does not match the server sending it according to the email header.

I contacted the company blocking us and this is what they say: " The error is saying that your outgoing email server's IP address does not match the server name of the email server record for your domain. We do a reverse lookup on all the incoming email to make sure it is coming from a legimate source. Since your email server is different from what you domain says it is, your email is dropped. Your IT needs to fix that."

Only emails sent through Zoho are blocked. Is there any way we can fix this short of me adding zohomail.com to my domain's MX record?