Conseguimos resolver esse problema graças à dica dada por joeqwerty. Não estávamos usando redirecionamentos de ICMP para redirecionar o tráfego. No entanto, o servidor proxy e o roteador estavam enviando redirecionamentos de ICMP para os clientes. Como nenhum dos dispositivos tinha qualquer utilidade para esse comportamento, desativamos os redirecionamentos de ICMP nos dois dispositivos e o problema nunca voltou.