>Decentralised search is hard, but I'm fairly optimistic once a basis is laid out, someone smart takes on the challenge (and is able to solve it, too!).

Check out http://yacy.net, you may be surprised!