В том то и дело, что проблема именно в NAT. Самому серверу все равно, какой ip используется, так как в его настройках не хранятся данные по ip, а вот SC и игре-клиенту нет. SC использует внутренний ip для соединения с сервером, а клиенты внешний ip. Поэтому надо пересылать udp-пакеты с порта внешнего ip на порт внутреннего ip и здесь без NAT не обойтись.