Hmm ... você não menciona como funciona a conexão entre os dois provedores. Você está usando um protocolo para fazer o failover dos dois juntos para que eles fiquem invisíveis para os usuários finais, algo como zeroshell linux?
Ou você está usando algo que é baseado em hardware e apenas disca para um segundo provedor quando é necessário?
Quando há problemas de conexão, todas as máquinas estão tendo o problema ou apenas uma ou duas? Se forem apenas algumas estações de trabalho, não ficaria surpreso se estiver armazenando em cache uma rota ou entrada de DNS e o traceroute estiver atualizando algo ou redescobrindo a rota para levar ao gateway adequado.
Você pode querer reexaminar seu gateway e encontrar uma maneira de tornar o gateway autoritário para todos e fazer com que o dispositivo de gateway (ou servidor) funcione como um balanceador de conexões e resolva o caminho que os pacotes devem seguir. da rede interna, se não é isso que você já tem.
Talvez mais informações sobre como a rede está configurada possam ajudar a diminuir o problema?