Could you direct me to more elaborate discussion why work in proof of work must be useless?

Am I wrong thinking that any problem with hard to find, but easily verifiable solution, should be ok? It would be nice if it had easily adjustable difficulty to scale it with processing power of the miners.