Nossa equipe de rede resolveu o problema. Foi um problema com a configuração do Netscaler; de alguma forma, não estava passando os pedidos - que tinham o número da porta no cabeçalho, para corrigir o IP (onde o WebService estava hospedado). Desculpe eu não posso explicar a resolução do NetScaler em detalhes. Eu perguntei duas vezes às pessoas da rede e a explicação delas passou pela minha cabeça. Mas, em qualquer caso, se alguém tiver problemas semelhantes, confira as configurações do Loadbalancer, do DNS e do Firewall.