DNS Records Missing

DNS doesn't actually "discover" machines in the domain.  In other words, it doesn't actively go looking for anything; it simply waits for clients to register themselves.  You shouldn't normally need to purge all of your DNS records unless you're having serious issues, but if you do, the quickest way to do so would probably be to delete and recreate your lookup zones.  Machines in your domain may experience connectivity and/or authentication issues while you're doing this, but it doesn't take long.

In the DNS console, you'll see at least one forward lookup zone, with the same name as your domain, and you may see a second one named _msdcs.(domain), depending on how your DNS is set up.  (Alternatively, _msdcs may simply show up as a folder inside the domain zone.)  Delete those zones, then create new ones with the same names as the ones you deleted.  You can do the same with your reverse lookup zones if you want to get rid of all of your PTR records as well.  Make sure to allow secure dynamic updates on all new zones.

As soon as you recreate the zones, open a command prompt on your DC and type "ipconfig /flushdns" and "ipconfig /registerdns".  This will flush the resolver cache on the DC, then register its A and PTR records.  Next, restart its Net Logon service.  This registers all of the DC's SRV records, which are necessary for machines in the domain to recognize it as a DC.  You should soon see records and folders appearing in the forward lookup zones if you refresh the DNS console.

You can then run the "ipconfig /flushdns" and "ipconfig /registerdns" commands on your clients to force them to register themselves, or you can wait for them to do it automatically.  (Flushing the cache is not always necessary, but it can't hurt.)