Navmesh agent stuck on partial path

We have a problem with navigation. As on the attached image we have a city being cut in two halfs by a river with few bridges. When we try to send an agent to a far away destination on the other side of the river it finds only partial path, so it walks to the closest point to the destination it can find (which is on the river edge) and gets stuck here. One obvious solution we've found would be to place special points on the both of the bridges' edges as sort of "waypoints" and send stuck agents to those if they can't find a full path. But since we are generating a lot of levels we would prefer more "procedural" solution than manually placed points. So two questions:

Is there a better solution to this problem? Since obviously there is a correct path we'd like to know what is the range in which agents stop looking for correct path and start doing what we described? And can it be changed?