O bom caminho seria fazer isso no lado da rede, com dois rotas usando o HSRP para compartilhar o mesmo IP. Com isso, se um roteador ou um link falhar, o segundo roteador levará o IP do primeiro (essa é uma explicação básica). Com isso, você tem certeza de que o gateway padrão dos seus computadores funcionará. Agora, se você realmente quer uma solução no lado do servidor, eu acho que pingaria algo na Internet (como o servidor IPS dns como Dave Cheney diz, mas também sei bem site como google e yahoo pode ser) e também verificar com tcpdump / ethereal se eu receber pacotes da Internet. Porque, por qualquer motivo, o ICMP não pode responder, mas o link pode estar em bom estado para que você provavelmente veja dados de entrada (da Internet) na placa ethernet do servidor.
Edit: como você adicionou "Estou procurando uma solução confiável, possivelmente não baseada em ping, software." Eu poderia sugerir monitorar ambos os roteadores com SNMP, se isso for possível. Ajudaria se você nos dissesse que tipo de roteadores são usados, se você pode acessá-los e assim por diante.