450 4.7.1 smtp SERVFAIL error on DNS 'SPF' lookup of 'domain name' Recipient address rejected

Thank you for looking at my question,

We run MS Exchange 2003 as part of SBS 2003. Users have started having mails to individuals at one company bounced back with the following error message:

You do not have permission to send to this recipient.  For assistance, contact your system administrator.

<ourdomain.com #4.7.1 smtp;450 4.7.1 <johnsmith@theirdomain.com>: Recipient address rejected: SPF-Result=ourdomain.com: 'SERVFAIL' error on DNS 'SPF' lookup of 'ourdomain.com'>

I don't even know where to start with this so any and all help would be appreciated greatly.
Who is Participating?
Paul MacDonaldConnect With a Mentor Director, Information SystemsCommented:
The recipient server is configured to reject mail where the sender doesn't have a valid SPF record in DNS.

Check to see if your DNS contains an SPF record and, if so, that it's valid for the domain name you're sending from/as.

All Courses

From novice to tech pro — start learning today.