Você deve confiar nos registros do seu firewall para rastrear conexões de Internet de saída e mapeá-los para os endereços IP internos que os originam. Qual roteador / firewall você está usando para o seu NAT? Mesmo uma caixa Linux rodando IPTABLES pode fornecer esse tipo de registro.
Outra opção seria configurar um proxy, forçando seus usuários a usá-lo e, em seguida, usar seus logs; mas isso, é claro, se aplicaria apenas ao tráfego da web.