Parece que minha configuração estava ok. Como se viu, o Edge no Windows 10 Mobile ainda não suporta a Autenticação do Windows (oh, a ironia) e os navegadores no Android Tablet também não funcionaram com a Autenticação do Windows. Então, foi praticamente uma suposição prematura de mim. Espero que isso ainda ajude alguém.
Solução: teste mais dispositivos e descubra se o navegador que você está testando deve funcionar com a Autenticação do Windows. Dica Pro: Você pode usar Gateways como Sophos ou TMG para solucionar esse problema, porque será apresentado um formulário de login que passa internamente as credenciais via Autenticação do Windows, porque o Kerberos não funciona na WAN (não é possível conectar-se a DCs).