IP address is not allowed to send mail from DOMAIN

Solution 1:

If it's being blocked due to an SPF record, then ideally they need to correct their SPF records to include their sending MX hosts.

The reason it will be blocked by your mail servers and not others is purely down the configuration of mail servers or relays in your organisation to honor SPF records of the sender. Other organisations chose not to honor SPF.

If I'm ever in the same position as you, I would normally temporarily whitelist the sender (if that's possible on your mail server/mail relay/spam filters) so it avoids the SPF check if required, and encourage them to change their SPF records.