There are a few things to check:
1. Name resolution
2. IP connectivity
I'd probably check them in that order. Find the Sitelist.xml file on one of the clients. That will contain the hostnames and IP addresses the client believes it should be using from its install (or last communication if it had one).
As an example, if your ePO servers FQDN is epo.mycompany.local with an IP address of 10.0.0.5 then neither of those would work from a regular internet connection. The name isn't resolvable by public DNS and the IP address is non-routable. There are options to change this (or this is a case where an agent handler might help).
Need more info before we can offer more assistance.
beside what Peter was saying, please note that VPN connection might result in such a behaviours in which the clients just disappear from, or not showing in, the tree. Please look up articles in VPN topic within McAfee Kb, there are a few things that you can do based on various ePO versions (what a version might allow to do and what another).