Would it not be possible to build a distributed routing table?
Have each node know it's position (lat/lon) and the position of it's nearest neighbors. When you send a packet, you send it to a lat/lon, and every node that sees your packet just tries to nudge it a little closer, until it gets there. Then to speed things up on the return trip we can ask each intermediate to add their position to a list on the packet.
Of course, moving nodes present a bit of a problem. Because they will keep attaching and detaching, there returning packets won't know where to reach them. I suppose if you knew your route through space you could send "scout" packets ahead of you, feel out the terrain, and prepend those positions to the list of your packets (so that they can find you when they return).
Dealing with changes to the (static) topology and also rogue nodes (ones that misbehave, drop packets, lying about their position, etc) are interesting problems. I think they can be solved.
The addresses must have meaning and hosts must self organise into a subnet based on connectivity, which feels like a np-hard problem... That does not imply that there is no reasonably well working approximation that works more or less as good except for edge cases. (Literally, ha...)
Addresses are simply bitstrings of some length.
If my address is a=a1a2...an, I need to store the first segment of the shortest path to each r_1=a'1a2...an, r_2=a1a'2...an all the way up to r_n=a1a2...a'2, where a'k != ak (i.e. all the addresses with a hamming distance of exactly 1 from me). I then simply route a message with an address b=b1b2...bn to r_i where i is the first non-zero bit of a xor b.
The problem, as with most P2P-networks, is that its not resistant to high network churn.