Any new ideas for how to solve the puzzle?
That's the problem: there are too many options. So, I have many ideas, I thought about sethdseed "privkeyForBrainwallet", because it is simple, and because it meets all conditions. But still, there are endless options that can be used as a privkey. Every time when there are some 32 bytes, then you can put there any hash, so the whole process can be unsafe, but the whole security comes from the algorithm. And if it is needed to mine something, just to get some 32-bit offset (or rather 36-bit offset), then it is even harder, because then every new way costs a lot of hashing, even if it is solvable by any CPU.
Also, when it comes to mining transactions, it can be just some kind of timelock:
https://www.gwern.net/Self-decrypting-files