Kind of old but I recently had this issue on a Network I just took over to manage.
Most of the time you will not get this if you only have 1 DNS server on your network, when you do have at least 2, the issue is most likely a sync problem.
As simple as it is, most of the time the issue will be with a machine on DHCP connecting to one with a static IP and the last one using a different DNS server than the one on DHCP. Hence, running an ipconfig /flushdns sometimes will work.
Now, how do you solve the issue? If you are not an Administrator... talk to one and/or run the ipconfig /flushdns and try again. If you are an Administrator, I will start by reviewing the DNS setup of the NICs of each DNS server. The primary DNS IP should another server and not the current IP, the secondary IP can be either another server or the current one, then manually go and add a loopback 127.0.0.1 .
As a test, to now everything is ok, take a machine and place a static ip on it, flush the machine DNS and register the machine (ipconfig /flushdns, ipconfig /registerdns). Check you DNS servers for the machine once all your servers have the same info, swap the machine to DHCP and run a refresh on the scope the machine have to be found, if doing this on all your servers shows the machine with DHCP then your issue is solve, if not then you should have to start checking the way the zone is getting updated.
In my case, after reviewing and changing the DNS IP servers settings on each DNS server fixed the issue and they take only a few seconds to be synchronized.