Hmm. Interesting. Groups of nodes could listen to each other and coordinate a search. Its sort of a way to get people to run nodes and keep them on. Possibly, a way to give out rewards on a regular basis, like a mining equivalent for running nodes with correctly configured ports.
However, GPU and ASICs would kill that approach as well, in the end, unless you could tie nodes to the search process:
https://en.bitcoin.it/wiki/Vanitygen
http://bitcoin.stackexchange.com/questions/28223/use-multiple-gpus-with-oclvanitygen
A small treasure (well, 0.25btc) is sitting out there in an address waiting to be found.
https://www.reddit.com/r/Bitcoin/comments/3i1l6m/a_small_treasure_out_there_on_the_internet/
Looks like going big, possibly with monthly payouts on easier addresses, is the way to go.