i had the same/similar issue in my environment. The solution is:
- change TTL for negative DNS cache, or deactivate it
- disable DNS cache in WinInet API
If it will work for you, then you can play with TTL's to make it suitable for infrastructure.