We have a rather weird problem where several customers are periodically unable to send to our domain. The problem is very hard to replicate, and I'm 99% sure the issue is on their end, but I'd like to pointpoint the issue, and need some ideas on where to look.
The NDR they receive is:
"This message was created automatically by mail delivery software.
A message that you sent could not be delivered to one or more of
its recipients. This is a permanent error. The following address
domain has no validd mail exchangers"
However, as I said, our MX records pass all the SMTP tests, and most users have 0 problems. When testing their MX records, I get Reverse DNS mismatch ("Warning - Reverse DNS does not match SMTP Banner"). Could this be related to the issue?
Any other ideas on where to poke around would be helpful. thanks!