Depois de muita pesquisa e lendo este ótimo artigo , descobri soluções: diminuindo net.ipv4.route.gc_timeout
para que as entradas do cache sejam removidas mais rapidamente e diminuindo net.ipv4.route.gc_interval
para que o coletor de lixo seja executado com mais frequência.
Mas tudo isso é temporário, já que em nossa máquina ele só resolveu o problema por algumas horas e uma coleta de lixo mais intensa exigia muito da CPU. Cuidado com a modificação desses valores - eles podem matar sua máquina.
Aumentar rhash_entries
parece ser o único caminho.