Você está descrevendo um algoritmo chamado "Path MTU Discovery" e funciona na maior parte do tempo. Apenas ignorantes sysadmins e produtos com bugs bloqueiam todas as mensagens ICMP. Até mesmo os sites que optam por bloquear Ecos ICMP (pings) são geralmente inteligentes o suficiente para permitir que as mensagens de Destino inacessível do ICMP sejam exibidas.
E, sim, um bom gateway NAT e implementações de firewall SPI examinam os cabeçalhos capturados dentro da mensagem Destination Unreachable do ICMP para descobrir qual fluxo corresponde e manipulá-lo adequadamente.