Так, ложная тревога. Точнее не совсем:
Похоже что в Windows и в Linux разные пинги (кстати чем?) Потому что из под Linux за NAT всё нормально пингуется, а под Windows — как описано выше.
Так же нашёл тему на провайдерском форуме где обсуждается эта проблема. Это проблема у провайдера на одном из узлов маршрута. Он в периоды нагрузок начинает глотать icmp и может еще что-то.
Вот заускаю на одной машине openSUSE на другой XP начинаю пинг и вижу: на одной 0 потерь, на другой ~7%
Ну и явно проблема у провайдера потому что зависит от времени суток. Вот сейчас в полдень потерь нет совсем и это «совсем» постепенно началось где-то часа в 2 ночи.