3 IP/port combos (internal address, NAT gateway, destination) and a timestamp is ~110 bytes. So for, say, 1 million distinct flows started per customer per day, that's 110Mb.

So no, storage sounds relatively reasonable to me so long as the retention period isn't too long.