O MTU é um problema de link local em termos de "funciona" versus "não funciona". Se as máquinas em ambas as extremidades estiverem configuradas para usar uma MTU apropriada para seu link específico, os roteadores no meio deverão fragmentar os pacotes conforme apropriado para obter dados. O desempenho será prejudicado, mas você deverá obter tráfego, mesmo que os ICMPs estejam bloqueados no meio.
Claro que isso não acontecerá se os roteadores entre tiverem um ou mais links com um MTU configurado incorretamente, mas alguém provavelmente teria percebido isso antes.
No que diz respeito a verificar onde / se o ICMP está bloqueado, sugiro traceroute. Se você estiver usando o Linux, a versão mais recente no Ubuntu vem com uma descrição moderadamente detalhada dos problemas relacionados ao bloqueio de ICMP, e isso deve lhe dar uma boa pista de onde o bloco está vindo. Desde que você tenha acesso em ambos os lados, você deve ser capaz de verificar em cada direção.