Вы описываете алгоритм под названием «Path MTU Discovery», и он работает большую часть времени. Только невежественные системные администраторы и продукты с ошибками блокируют все сообщения ICMP. Даже сайты, которые предпочитают блокировать эхо-запросы ICMP (эхо-запросы), обычно достаточно умны, чтобы пропустить сообщения ICMP Destination Unreachable.
И да, хорошие реализации шлюза NAT и межсетевого экрана SPI смотрят на захваченные заголовки в сообщении ICMP Destination Unreachable, чтобы выяснить, какому потоку он соответствует, и обработать его соответствующим образом.