Anything with a use has value to a person benefiting from that use. The trick is to make it such that out-of-band payments to specific miners are not likely to occur.

That's not to say that it's absolutely, 100% a priori impossible to have a "useful but no-value" proof of work. Only theorized example I know of is time-lock decryption: you have a deterministic process for generating public keys, and the proof of work solution is the recovered private key. However this invalidates other assumptions that are required of a secure proof of work, at least with all existing public key crypto systems.