The problem you describe has many layers.
First and foremost, I have never set foot into an organization that actually had as many active desktops in their environment as they said they had -- they always over-estimate by at least 10%. The primary reason for this is that they rely on Active Directory
which is in no way an actual inventory of active systems. Thus, the first task is to always clean-up AD so that only truly active machines have accounts.
From there, you need to examine the discoveries being used. AD System Discovery is the most common and reliable (if AD is cleaned-up that is) but AD System Discovery will *not* create resources for system objects in AD that are disabled or that it cannot
resolve using DNS. The DNS resolution check is meant to try to filter stale systems because those systems should have been scavenged from DNS but there are many other reasons why systems may not properly resolve. You also of course need to ensure that AD System
Discovery is configured to find all applicable systems in AD.
Even with this basic filtering, as mentioned, just because there is a resource in AD, doesn't mean that the system actually exists, is active, or is even communicating with the domain on a regular basis.
Basically, it's not ConfigMgr's fault if it can't find and manage every single system that an organization *thinks* that it has and it cannot overcome permissions and firewall issues; it is not omniscient or all powerful and expecting it to be is plain silly.
Start with the reports as they will definitely guide you and tell you which systems it cannot communicate with (to push the client) and/or which systems had a client install failure. You can also examine adsysdis.log and ccm.log manually to get detailed
information.
A common technique to get around any firewall issues is to use a startup script to run the client agent install instead of just relying on client push.
Other recent topics
