If that is not what happened, how did the wallets back then work? Would they generate a new change address at the time of sending? In which case there was no record of the private key?
This happened before deterministic wallets, which are relatively new.
At the time, the wallet would create a new, random "change" address when the transaction was created. This new address would exist only in the wallet, which would then need to be backed up.
At the time, a wallet was a collection of random addresses that would have to be backed up every time a new address was created. Now, HD wallets are pseudo-random addresses that can be recreated with one master key that doesn't change.