there are plenty of problems that are very expensive to solve and very easy to verify. all NP-complete problems are like that. all of these can serve as proof-of-useful-work, there's no need to demand proof-of-waste. plus, verification can also be made into proof-of-useful-work, if you're smart enough.

now, the token-granters need not really be concerned with any of that: it could be up to the customers paying for computing to be performed by other parties to figure out how to break up their problems into smaller verifiable pieces.

even if they're hard to break up, the architecture could have room for longer tasks that grant more tokens, that dedicated compute machines (as opposed to browser-based PoWs) could engage in.

I don't know enough about proteinfolding@home@mastodon.social to tell how verifiable the results are, but I know SETI@home@mastodon.social had verification built into the architecture. those are inspiring examples of very distributed computing architectures, not necessarily systems that could be trivially integrated into such a hostile environment as proof-of-useful-work systems.