O problema só aparece quando o endereço IP muda, correto? Se for esse o caso, você pode definir o TTL nos registros DNS individuais para 1 segundo. Isso impede efetivamente que apenas esses registros sejam armazenados em cache.
Você também pode desativar o serviço do cliente DNS nas estações de trabalho. Isso impede que o cache funcione também, mas afeta todas as pesquisas de DNS, não apenas aquelas em que você está interessado.