Algum tempo depois... o problema está parcialmente resolvido, então vou atualizar a situação para o caso de alguém ainda querer contribuir:

Os túneis EoIP estavam muito instáveis, caindo em situações de pico no router A, então troquei tudo por bridges de VLAN nos routers todos que estão na rota entre ele e o PC Linux e isso estabilizou a coisa toda.
Resolvi fazer alguns testes de port forwarding usando o router C diretamente, ao invés do A. Eis que funcionou! As mesmas coisas que estava fazendo no router A fiz no C. Um detalhe que determinou tudo foi o gateway padrão do PC Linux. Com o gateway sendo o router C, tudo funciona, mas se eu mudar para algum router na rede bridge de VLANs, embora tenha conexão com a Internet normalmente, o port forwarding para de funcionar.

Ao meu ver, esse comportamento é muito estranho. Uma conexão não deveria depender do gateway do servidor para achar seu caminho de volta, de resposta. Bom, vou ter que deixar da forma que está, ao menos o objetivo principal foi atingido que era permitir acesso externo a determinadas portas do router C e PC Linux, embora não tenha sido exatamente da forma que planejei.