It is impossible to create a "useful" PoW. The issue comes down to incentives. As bitcoin is a decentralized, trust-less system, there needs to be constant and powerful incentives to prevent miners from cheating (by creating forks, or executing any number of other attacks).
The current main incentive against cheating is that miners will lose their invested PoW (compute time + electricity) if they cheat and get their block thrown out. However, with a useful PoW, this calculus changes. Now, the PoW is no longer "wasted" when the miner cheats and gets caught as the PoW is now useful for something besides mining. This means that attacks are much cheaper and much more likely to happen.
One interesting part about this is that you can consider PoW usefulness on a sliding scale. The more useful the PoW, the more vulnerable your coin is to attack. Thus, you can probably get away with a "useful" PoW if it isn't actually very useful. This is one of the reasons why most "useful" PoW schemes focus on something which is pretty much useless (such as finding weird primes and whatnot).