But I am not sure how P2PK worked. Has the public key changed every time for early wallets?
The same as any other output script but instead of using hash of public key you use the same public key. It could be reused or the wallet could produce a new pubkey for every new payment (which was the default).
So the default was that the mining reward of 50 BTC was sent to a different public key each time?
It would favor the scenario of "gradual breaking" the keys rather than "grab all at once".