Well, you've checked RBL and SPF's, that's a good start. I'd say that they're employing a commercial SPAM filter and either your IP, or the IP address block range of your provider has been marked as a SPAM sender.
I take it that you can connect via telnet to their MX record address, so it's not an outright rejection.
It's probably only a SPAM filter and nothing more serious. Give them a call and ask them to follow it up with their mail provider.
Dave
|