У меня была аналогичная ситуация с клиентом. Контроллеры домена были неправильно сконфигурированы (в режиме NT4), и IE проверили опцию "Enable Windows Integrated Security".
То, что делает IE, когда в Windows Integrated Security режим - он, пробует запрос Windows 2000 + билет режима AD/Kerberos. Когда веб-серверу не удается аутентифицировать билет, он возвращается к состоянию до сбоя к NTLM.
У Вас есть 3 опции.
К сожалению, в моей ситуации, я должен был пойти с опцией № 2 из-за включенных эго, но она работала исключительно хорошо.
Просто размышление вслух здесь, но является клиентскими машинами на домене или в рабочей группе?
(Да, если бы у меня был представитель, то это было бы комментарием!)