Yeah I believe that's the problem, the work needs to be trivially verifiable. You also need to be able to modulate the difficulty easily so that the blockrate remains constant as more people enter the "contest". And of course the work itself must somehow reference the transaction data otherwise you could use the same proof of work for two different blocks.

Seems difficult to find an actually useful mathematical problems that fits all these prerequisites.