Scavenging в свойствах сервера включите. Если у Вас несколько серверов - лучше сделать это только на 1-ом. Устраевшие записи динамические, или static? Если статические - их нужно руками чистить. Проверьте время аренды для вашего пула на DHCP. В идеале срок жизни записи в ДНС без апдейта должен составлять такое же время как и срок аренды у DHCP. Срок жизни записи в ДНС состоит из No-refreshInterval + RefreshInterval. Если время TimeStamp + No-RefreshInterval + RefreshInterval стало меньше текущего времени на ДНС сервере - то при следующем старте Scavenging запись будет удалена.