Sem o protocolo em questão, é impossível dizer em detalhes, mas parece que você está sendo deliberadamente vago, então eu vou responder em geral.
A partir de sua descrição, o servidor / protocolo não pode manipular o NAT, em vez de negociar uma sessão com cada cliente em uma nova porta para saber quem é quem projetou simplesmente responder a um IP de origem listado nos pacotes de entrada. Isso é bom apenas para LAN.
Para subverter esse problema, você precisa criar uma VPN ethernet em ponte, OpenVPN ou outros, mas isso é significativamente mais difícil de configurar do que uma VPN de nível de IP regular. Além disso, como você não pode modificar os clientes, você precisaria ter o seu roteador como um cliente VPN, portanto pode ser necessário substituí-lo. Você pode hospedar a VPN em qualquer máquina da rede que possa executar o software X86.