Steven,
It sounds like it could have been a Reverse DNS issue.
If the server that sends notifications has a different IP address than it had before it could cause this kind of random problem.
Some ISPs do a domain name lookup to see if the IP address the e-mail is coming from matches the IP that is registered to the e-mail domain name, if not, it is treated like Spam and discarded.
It can take awhile for the change they made to propagate throughout the DNS servers around the world.
I have had this same issue that I have had to resolve in the past.
Hopefully this fully resolves the issues.
Brad
It sounds like it could have been a Reverse DNS issue.
If the server that sends notifications has a different IP address than it had before it could cause this kind of random problem.
Some ISPs do a domain name lookup to see if the IP address the e-mail is coming from matches the IP that is registered to the e-mail domain name, if not, it is treated like Spam and discarded.
It can take awhile for the change they made to propagate throughout the DNS servers around the world.
I have had this same issue that I have had to resolve in the past.
Hopefully this fully resolves the issues.
Brad
Comment