SMG Blocking Messages "...Server is Not Trusted"


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". I'm thinking this might be an SPF issue on their end.  What is the best practice for this situation? Shall I just whitelist their server (probably bad practice)? Or, send their IT department a message? Would like to confirm it's an SPF issue tho.