Eu descobri o que estava errado. Nós tínhamos duas máquinas com o mesmo IP em nossa sub-rede, então houve o conflito. O cliente estava tentando se conectar a alguma outra máquina, que nem sequer escutou o protocolo XMLRPC.
Eu achei que funcionaria se eu esperasse, digamos 15 minutos, mas não .. ele simplesmente funcionava aleatoriamente para uma ou duas ligações. Tudo faz sentido agora.