Ich bin wie Kathmai der Meinung, dass das ein DNS Problem ist.
Ist im Zusammenhang mit einem IIS aber nicht von Vorteil wenn kein DNS Server läuft. Ohne den ist es fast klar, dass der nicht funktioniert.
Kann es evtl. Probleme mit (abgelaufenen) Zertifikaten geben? Wie wäre es, wenn ihr bei den Problemrechnern zum Test die Adresse des Servers mal in die Hosts eintragt (wenn die Verbindung zum IIS per DNS abläuft)?
Habt ihr mal probiert, den IPv6 Support abzuschalten? Ich habe da in den letzten Tagen/Wochen teilweise massive Probleme gehabt, dass unser DNS Server auch abgeschmiert ist.