We have a really weird issue. We cannot receive emails from a domain that is using Postini filter services. It's telling them that their email was rejected because of an SPF check failed- on relay of Mail from <firstname.lastname@example.org> SMTP error code is 550.
We do not have an SPF record set up. According to Postini they do not check the SPF record. We can send to them just fine. We can receive email from 1 person there, and no one else. That's what's making this weird. I never see it hitting our Exchange 2003 server. We were talking about setting up an SPF record, but this is the only company we are having issues with. We both recently changed ISP's. They also recently got a new mail server.
What else should I check? How do I solve this issue?