I've been having this problem with Verizon for months, and I finally have fixed it. The problem is that Verizon will not accept email without first verifying the sender through a separate SMTP connection, but that Verizon's own servers are misconfigured so that they do not pass a reverse DNS RFC931 check. I had a TCP Wrapper that was rejecting SMTP connections that failed the check - hence the problem.
So it works like this:
An email is sent to Verizon. Before accepting the email, Verizon attempts a SMTP connection with the sending server:
However, Verizon fails the reverse DNS check:
My hosts.allow file had this line:
Once I commented that out, the Verizon mail got through.
Of course that line was there for a reason -- Verizon's anti-spam measures coupled with their own misconfiguration of their reverse DNS requires me to abandon my own mechanisms to protect against abuse of my mail server.
But at least I've solved the mystery.
It's possible that this only happens with email that Verizon suspects is spoofed -- this seems to be a problem with one particular server of mine that sends automated emails with a reply-to that is from a domain with mail handled on a different server. I have configured SPF to make it clear that mail from mydomain.com should be allowed from either IP, but it looks like Verizon is doing its own checking. In other words, the email comes from domain1 at server A; Verizon's reverse check shows that domain1's MX resolves to server B - so Verizon initiates an SMTP call to server A as a second check. But... as noted .. Verizon's connection to server A fails because of the fail the RFC931 check.
