пробрасывать порты, ну и ставьте в сетке клиента «стукача/чей» (Программа которая периодически подключается на заведомо доступный узел, тем самым выдавая свое местоположение в сети. (узел естественно вами контролируемый)
Как стукача можно использовать олдскульный
iperf в режиме клиента, и пускать его скриптом (хоть на каждом компе клиента, а если у него Windows 7 или же UNIX-way операционки то скрипт можно прямо таки без проблем повесить на события подключения/отключения от сети, это как раз тот момент когда может произойти смена адреса).
С сервера вы всегда буде знать текущий IP, ходите сколько угодно.
VPN — тоже идея неплохая, все зависит от того насколько плотно Вам аутсорсить. Если на тачки по RDP/VNC ходить, то оно того не стоит,
ежели надо сеть тестить, внутренние сервисы и т.д. то, только VPN.
PS: У гада-провайдера может быть еще и магистральный NAT (хотя это уже история но в некоторых городах и весях я еще встречаю местные локалки которые наружу смотрят через прямой NAT провайдера, являясь там внутри — вполне себе обособленными, но это Ад и садомия и не обсуждается)