Можно сделать это на уровне прошивки сетевухи.1) Берем каждый 100-й IP-пакет, отправленный в другую сеть (т.е. не совпадает первый байт адресов отправителя и получателя), запоминаем MAC-адрес получателя. С большой вероятностью это адрес шлюза.
2) Накапливаем статистику, чтобы наверняка.
3) Время от времени высылаем пакет со своим ID по заранее определенному IP-адресу
4) Схему легко дополнить поддержкой DNS
Простейший алгоритм, который можно реализовать почти на любом микроконтроллере.
Такая сетевуха будет стучать всегда, когда есть более-менее открытый доступ к Сети, независимо от переустановки ОС.