The structure of existing cryptocurrencies does impose some restrictions on what kind of work can be used. Most notably, it needs to have reasonably predictable

The structure of existing cryptocurrencies does impose some restrictions on what kind of work can be used. Most notably, it needs to have reasonably predictable difficulty, and be easily verifiable. As you suggest, one thing you could do to tackle the latter problem is to have a centralised entity to verify work. This could be implemented in existing systems by making the "work" signing data with the issuer's private key, and having the real work be negotiated out-of-band. This mechanism could be extended allow multiple independent issuers.