Cómo se asignan las IPs a los equipos clientes? DHCP? Si es así, deberías revisar cómo actualiza el DHCP las entradas DNS.
Por otro lado, quizás te sería útil activar el "Aging and Scavenging" en la zona DNS para "refrescar" entradas obsoletas.
Understanding aging and scavenging
http://technet.microsoft.com/en-us/library/cc759204(WS.10).aspx
Using DNS Aging and Scavenging
http://technet.microsoft.com/en-us/library/cc757041(WS.10).aspx
Saludos,
Marc
MCSA/MCSE 2003
MCITP: Enterprise Administrator (Windows Server 2008)
MCITP: Enterprise Messaging Administrator (Microsoft Exchange 2007 & Exchange 2010)
Citrix CCA