They don't. Resilience isn't additive. The more nodes you add, the more announcements and traffic you add, which congests the network further. Regular internet topologies work because of high throughput backbones.

my impression was that there are algorithms that work well (dont remember the name sorry), and they don't really keep track of the entire network per node, each node only has a heuristic idea of how to route packages both to local and faraway neighbors.

This is very much like pathfinding in a video game - you know how to get to a next the next grid square, and also your region you are in knows how to get to its neighboring ones - recursively to the top, but said info is distributed heuristically through the network.

Also, meshes need not be composed of constantly moving and changing nodes. An example of a neighborhood of houses or radio towers, where each node is semi-reliable and doesn't really move is an absolutely valid and real world use case.