The difficulty is that the problem must be of a predictable complexity. In other words, you must know ahead of time how long it takes a given amount of processing power to find the solution.
Would predictable statistical distribution of complexity not be enough? As in, you get a randomly assigned job, that takes on average a given amount of processing power, and is proven to not need more than some upper limit - or even, you time out after a given amount of processing power and request a new job.
And ideally have each unit small enough that mining will completing multiple jobs so difference in complexity starts averaging out.
You'd also need to be pretty certain that no-one's going to come up with a faster algorithm for solving the problem. I can't think of any real-world problems to which all these criteria would apply.