Which sites can they access and which not? Can they ping the IPs in question? Do the hostnames resolve?
What does “no longer receive mail” mean exactly? How did you find out / what happens instead? Who can send and who cannot? Any error messages in the /var/log logfiles?
We need much more information about your network structure and problems to give any meaningful advice.
Yeah, as Locutus mentioned, we’ll need some additional info to help dig into that one… it would be especially helpful to have an actual domain name that’s having a problem. You can always go back later, edit your post, and remove it, if you don’t like the idea of posting your domain names here
Also, is your server on a public IP, perhaps on a DMZ? Or is it using a private IP address?