But you could turn it around into finding factors of a very large number to check whether it is prime.
Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...
A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor anybody can quickly check whether it actually is a factor.
Then some formula using the previous number and the factor that has just been found is used to create the next big number to check.
Of course there is the problem that if the number is actually prime we never find a factor. This isn't an answer just an idea of what sort of thing the pow problem might be.
There is a lot of processing power out there working on hashing. What if a researcher wants to use this sort of distributed processing power for a useful research project? Everybody donates their processing power to the project and they are then entered into a lottery with the chances of winning related to how much processing power they donate. This lottery replaces the lottery of whether or not you come up with the right nonce.