>  (Есть подозрение, что на пути что-то режется).

Вот с симптомов и нужно начинать. Может ваша проблема не стоит и выеденого яйца.

Попробуйте iperf в связке с shell скриптами.
Или любым удобным ЯП (php, python) посылать пакеты. На другой стороне слушать tcpdump/wireshark или те-же самые простые приемники TCP/UDP пакетов на тех-же самых ЯП. Есть пакет определенного содержимого - переключаемся на следующий порт. Нет - выводим алерт или мессагу в файл с номером порта.
Доработать простые примеры TCP/UDP клиент-серверов из интернета дело одного вечера.

> Вопрос: Какой программой можно открыть сразу все порты, что бы они откликались на NMAP?

У вас IP-стек ядра ОС не сдохнет слушать сразу на всех портах TCP+UDP да еще и отвечать в обратную сторону?