"Провайдер клянется и божится, что у него все идеально" и
"Кто-то видит некоторые "левые" устройства, которых быть не может. Но при попытке обратиться к этим устройствам (пингом, телнетом и т.п.) мы их не видим."
не стыкуется.
Либо провайдер не изолирует вас нормально, либо изолирует, а на вашей стороне есть кривая конфигурация.
Все микротики, которые работают на ROS и при наличии установленных advanced-tools, могут помочь с анализом мусора.
Определите, что за мусор и откуда он, дальше станет яснее.
Но это не поможет, если проблема всё же у провайдера.
Тогда останется один вариант - его смена.
В моём городе Ростелеком себя также вёл - "у нас всё в порядке, скорее всего что-то у вас".
Сменили провайдера - проблемы все ушли.