Is it normal for a DNS server to not have all sites? When you say they have likely been removed would that be an webhost issue?
The
root DNS servers have all sites. Below them there is a hierarchy of DNS servers which cache records for fairly short periods. The hierarchy terminates at the DNS server(s) that your ISP provides. Any server in that hierarchy can refuse to provide records, although the root ones never do AFAIK.
You might be able to run your own local DNS server; I've done that when my ISP's server was being flaky. Most can be set to go directly to the root servers, if they don't already. See, for example,
Top: Computers: Software: Internet: Servers: Address Management; MaraDNS might be interesting. However, your ISP or someone above you in the chain might be blocking requests to those IPs and ports.