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.
I guess I was assuming that the backup key passed to BitGo would be a root key. If they were generating child keys and BitGo's API accepted them, that would explain the backup keys being unique. I agree that generating new cold storage keys per user is impractical.