There are techniques to reduce the logging overhead, such as [http://tools.ietf.org/html/draft-donley-behave-deterministic...]. Basically give each customer their own range of ports on the NAT address so you only need to log that range.