Did you check their domain - ie. via mxtoolbox?

In case of reported issues talk to their IT department!

ebsr_paramedic said:

One user is reporting that recipients at one domain are receiving bounced-back messages from our server that their email is being rejected because their mail server is "Not Trusted".

Your Message Tracker and/or the SMG logs should provide additional information about why the message was not accepted.

If your SMG server is checking IP reputation it is possible that messages are being rejected because the IP reputation is not good enough even though there is nothing wrong with that IP address, perhaps because that IP address hasn't been used previously to send email!

I usually try to reach out to their IT, but much of the time they just snarl back why they have to make adjustments for us as if they are not the ones out of compliance with best practices, or even with fully broken configurations.

Mxtoolbox returned the following (images). Would this spf record issue cause smg to reject their emails?

Thanks for your help.

I've never seen a null dns spf record error, but I'd assume that would cause some problems.  That's a full on error, not just a warning.  Definitely something they'd have to fix.

Thanks RaveNet. Hi Kevin Boyle have you seen this error? Based on the Mxtoolbox test, do you still think this is a Reputation issue?

I did some more digging and found this (of course they will say my system is at fault):
https://support.valimail.com/support/solutions/articles/48001186312-why-do-i-see-a-null-dns-lookup-when-i-use-a-certain-dns-scanner-

..Then I found this >>>

As you have found out, it is their fault. And it is not ip reputation. It is simply spf mis-configuration...

You can be sure that you are not the only one who reject their mails.