Meses depois, descobrimos a causa. Alguns (mas não todos) dos servidores foram atualizados para uma versão mais recente do .Net Framework.
A Microsoft não suporta servidores diferentes usando o mesmo StateServer com diferentes versões do framework , então quando os clientes pulavam entre um servidor com 4.5.1 e um que tinha uma versão anterior eles essencialmente perderam a sessão e o aplicativo travou.
Se você encontrar esse problema, sugiro que você verifique qual Framework está instalado em cada servidor - todos devem ser os mesmos para que trabalhem com o mesmo StateServer.