Ouais bah donc 2 causes possible:
1) le client DNS de ton Windows bug, et à part le réinstaller je vois pas (si le problème vient bien de là)
2) Entre toi et le serveur DNS, un pare feu t'empèches de faire des requêtes DNS (en bloquant le port 53 en UDP (mais ca m'étonnerais)
T'as pas un live CD d'Ubuntu par exemple ? Tu pourrais tester pour voir si ca marche ou pas.