In truth we didn't give much thought to this yet. But I suppose it will be utilizing the hierarchical quad-tree index in some way, and/or reducing the problem by considering a smaller area.
Probably the navmeshes could be hierarchized, the segments assigned a level (like 0 for long distance routes, 1 for interstate and so on) and the algorithm would be selecting the level by the distance. This way it would not get lost in the detailed mesh when traveling large distances, it would use "highway" segments to cross the distance, detaching from it and using the more detailed meshes locally. Much like traveling by a road network I'd say.