It is possible that bitfinex did have a new cold storage key for every user, but I find this to be very unlikely as it would be hard to maintain for cold storage.

Rather it is likely that they had one cold storage master key and each users cold storage keys were generated from that. They probably had a derivation path of m/0/i where i would be a unique id for each user. Then the internal and external keys would be derived as normal from that prefix path.