I thought about this as well before, but the problem is that you don't want just ANY NP-problem: You want an NP problem (it doesn't even have to be NP-complete) that you can easily adjust the difficulty.
How do you adjust the difficulty on something like this?
Also, you always have to calculate the "hashes" of the blocks. I guess you could encode a block as a graph and it's "hash" could be the smallest path that visited all the edges, but how useful would that be?
When I looked into this in the past, I stumbled into Gridcoin[1], but I don't know how they deal with the difficulty/usefulness of the solutions.