Однако если делать трейс (команду mtr) видны потери на первом хопе порядка 80%.Если при этом на последнем хопе нет "потерь", если рабочий трафик обрабатывается нормально (без потерь пакетов), то не думаю, что это вообще проблема, скорее косметический нюанс.
С какой стороны начинать копать?Не являюсь знатоком сетевой подсистемы Linux, но предположу, что имеет место ограничение ICMP-трафика, сгенерированного хостом. Проверьте параметры ядра:
/proc/sys/net/ipv4/icmp_ratelimit
/proc/sys/net/ipv4/icmp_ratemask
/proc/sys/net/ipv4/icmp_msgs_per_sec
/proc/sys/net/ipv4/icmp_msgs_burst