I had very many issues with this in the beginning days using classic and corporate firewalls.
Since the members were all county,city employees.
Found out that shared IP's gets you grouped with all others on your host. Such as spammers.adult sites, etc.
So they would be blocked from access as well as the emails.
Took an extremely long time to get them resolved dealing with one city after another and still have some that pop up on occasion.
But the dedicated ip helps.
In this case not so sure but it may be the email server config.
