I don't have much experience with that so maybe this is all a stupid, but I think that routing in mesh networks is never scalable. It basically always requires all the nodes to keep a full view of the network in order to route packages -- and often there is no incentive for them to do that either. And then the thing is easily spammable but either that problem doesn't happen because the mesh never gets big enough or it has a central committee that decides who can join.
The biggest example is, of course, the big ICANN-controlled IP network, that gets all the negatives of being centrally controlled while weirdly getting also all the negatives of being a kinda-decentralized peer-to-peer ad-hoc network between indepent ISPs.
A good solution that makes kinda-decentralized (at least open and permissionless) routing possible and replaces node addresses with pubkeys could get rid of ICANN. Once that is done, ad-hoc peering would become more seamless and ISPs wouldn't have to be so big, clunky and centralized, they could slowly split, and non-comercial entities could join the party too by basically just plugging a cable or pointing an antenna at the correct place.
What is it?
One very dumb solution that came to my mind that has a chance of working is one in which each node as a keypair and to be reachable by others they announce their address -- for example, using some kind of DNS (on a [spacechain]?) or by directly communicating their address through some other means -- as their public key plus some "routing hints".
The routing hints are just pubkeys of other nodes known to be routers. Known to whom? Well, this would require some schelling points to naturally appear and the network would be ordered around them, but you are never forced to use them, you have to include as many routing hints as required to ensure that all the people you want to connect to you will eventually be able to, but nothing is ever 100% guaranteed.
Such network could probably work with a pure onion routing scheme with all its privacy benefits in some cases; degrading to a trampoline onion routing scheme otherwise, which means it will just be slightly less private the more trampolines you have to use. And every node has to keep track of just a set of routes from them to a bunch of known routers (or trampolines, which in my mind are mostly the same nodes, but are slightly different roles).
Example
Suppose A is trying to connect to B.
A is a home computer in the city of Évora, Portugal.
B is a home computer in the city of Udine, Italy.
There is a route (we, the narrator, know) between them that goes like this:
A--Ev--Li--Al--Ro--Sm--Ve--Ud--B, in which Ev means the node of an ISP in Évora which directly serves A, Li means a big node in Lisboa, Al a node in Algiers, Ro a node in Rome, Sm a node in San Marino, Ve a node in Venice and Ud a gateway node in the mesh of Udine to which B is connected.
There could be many other routes, but we'll ignore them for now.
B could have published his address as <pubkey-B>?hint=<pubkey-Ud>,<pubkey-Ve>,<pubkey-Sm>,<pubkey-Ro>, which would mean A would only have to know a route from Ev up to Ro.
If Ro is known to be a big router, A could easily have a route cached there, and could discover other routes by asking around every now and then too. It wouldn't take a lot of space to have routes cached to some thousands of different known big nodes like that. Then A can just wrap an onion with all the coordinates and the message inside and hand it to Ev and it would reach B. Inside the message she would also include the full route for a message to be sent back.
However, even if A doesn't have a route to Ro, it could still hope that Li would have, then she could make a special "trampoline" onion that goes Ev--Li and then when Li receives it it sees a request to forward the next packet to Ro, so Li has the freedom to choose a route from itself to Ro (as long as it knows Ro, of course) and from there A's message continues.
The same trampolining can exist on B's side, if B doesn't have a route from Ud to Ro, but knows Ro is likely to have one up to Ud -- or if B feels it's not worth including so many hints when most big nodes will have routes to Ud, for example, it can publish his address as <pubkey-B>?hint=<pubkey-Ud>*<pubkey-Ro> meaning that one should find a route up to Ro and from there ask Ro to trampoline it up to Ud.
Or, if B doesn't expect Ud to be very well-known, but Sm yes, then it could do <pubkey-B>?hint=<pubkey-Ud>,<pubkey-Sm>*<pubkey-Ro>. Again, this is just one hint, in practice it would have to have a lot (maybe 10, 20?) other hints, in a tree structure that this querystring syntax isn't very suited for encoding:
Ud
Tr
Pu
Za
Li
Sm
*
Ro
Ba
Mi
La
Ge
*
Mo
Tu
(Remember, we're using city name abbreviations here, but each of these would be a specific node, with a specific public key, supposed for the example to be in such a city, but nothing prevents them from being in different cities or that multiple nodes exist in the same city.)
Summary
Basically packets go from node to node, in a sequence established by the sender -- with optional trampolines in between -- until they get to the target. Target responds in the same route. Nodes can be anyone. Focal points form around big nodes, but they can be replaced easily, the receivers just have to stop using them in their hints, so the network is flexible and open.