What about checking signature size instead? In this way, z-value of the transaction can be indirectly checked inside Script, by checking the size of s-value of the signature. More details: https://bitcointalk.org/index.php?topic=5551080.0

I think it should be possible to do both with Merged Mining, but I don't know exactly, how to connect transaction mining with block header mining. Because then, users could mine regular Bitcoin block headers, and also use some of their power, to move some satoshis from some outputs, if they would commit into them.

It was beaten inside signatures by this example: https://bitcointalk.org/index.php?topic=5551080.msg65618511#msg65618511

Here, instead of grinding transaction hash, z-value of the signature was mined, which allowed using low s-value, and claim 55k sats as a reward:

So, as you can see, real satoshis can be deposited into puzzles, which could be claimed by those, who will mine such outputs.

And of course, it should be possible to do both: claim some reward from my puzzle, and then grind transaction ID, and claim some MHIN coins. But it would require more hashing (first my puzzle, and then the whole transaction, with additional power).