Acho que verificaria as coisas nesta ordem:
- Certifique-se de que os usuários com falha realmente atinjam o servidor da web com wireshark ou tcpdump. (Minha aposta é que eles não e você pode culpar alguém:)
- Verifique se há picos de carga ou outros bloqueios estranhos no servidor, por exemplo faça coisas como "encontrar / -tipo f" enquanto os usuários falham. Talvez desmonte quaisquer volumes NFS, se houver algum.
- Medição de ida e volta no servidor da Web, ativando o registro do tempo de ida e volta (no Apache isso seria LogFormat% D) ou usando wireshark para ver se o tempo é consumido no servidor ou no navegador.
- Instalando o Firebug em um Firefox em uma máquina com falha e observe seu diagrama de tráfego de rede para ver o que leva muito tempo (isso, é claro, presumindo que as etapas anteriores indicaram que o navegador realmente fala com o servidor).
EDIT: Mesmo se você não pode ir para o site dos navegadores com falha, talvez haja área de trabalho remota ou assistência remota para ajudá-lo?