Are there Guaranteed Proof-of-work Systems?
You could use a challenge consisting of multiple subtasks.

For example, provide a unique random string of characters $R$ and ask for $n$ distinct strings that have $R$ as a prefix and whose SHA256 sum ends in $z$ zeros.

In a single hash calculation, the probability of a lucky guess is $2^{-4z}$, so the probability of multiple lucky guesses in one challenge is going to be very small if $z = 10$.

The number of SHA256 calculations needed to pass the challenge is of the order of $n \times 2^{4z}$, but only $n$ hash calculations are needed to check the results (plus a little extra to check that no two strings are the same).