Это может быть глупая (извините) обработка сеанса, которая соответствует сеансам по IP.Все ваши пользователи NAT имеют одинаковый внешний IP, поэтому они объединены.Лучше использовать куки для обработки сессий.
Как говорит Белиариус, возможно, вы уже используете куки, но если куки создаются с IP-адреса, они очень бесполезны.
Если приложение, о котором вы говорите,не основанный на браузере, вам придется отправлять куки своим клиентам и самим осуществлять обработку куки.Или просто используйте одно TCP-соединение для каждого клиента и повторно подключитесь при повторном подключении.