#5.5.0 smtp;553 Error

[Theoran]

Our mail server is getting emails rejected by specific domains, some of them major providers like gmail.com, hotmail.com, yahoo.com and even live.com.

Here is the error message we get:

There was a SMTP communication problem with the recipient's email server. Please contact your system administrator.
<rediffmail.net #5.5.0 smtp;553 Sorry, relaying denied from that From address (#5.7.1)>

Here are the steps I have taken:
1) Validated that our MX and A records are correct
2) Called our ISP and had a PTR record added so the reverse DNS lookup works (4 weeks ago)
3) Ensured that we are not on a black list

We use nameservers provided by our hosting provider.

Any help you can provide is much appreciated.

[itrama]

5.7.1 means "refused due to some site policy of theirs"

Since they don't provide any specific information as to what the policy in question is, or why they think you have violated it, you will probably need to contact the postmaster at each of those domains and ask them.

The steps you have taken already to avoid this sort of thing are proper.

Double-check the outbound IP of your mail server is not in the bann list