In fixing this (http://forum.simutrans.com/index.php?topic=12299.new#new) issue in Experimental, it occurs to me that the problem is the same in Standard: the maximum routing depth for any given map is the minimum of the world's x dimension multiplied by its y dimension and the maximum routing steps set in simuconf.tab. This is not always sufficient for a ship going from one end of the map to another otherwise in a straight line (for example, avoiding islands).
This (https://github.com/jamespetts/simutrans-experimental/commit/57ad18278bb452b1fc8af9c79bfcc6b5830bf4f3) is how I fixed the problem for Experimental - I am not sure whether any of the Standard developers want to use a more sophisticated solution. (Note that this also solves a related problem where using the advanced settings dialogue to change the routing depth had no effect until the game was saved/reloaded as the nodes were not reinitialised on closing the window).
If there are less water tunnels and bridges than land tiles (never saw such a map) a routing depth of width*height is mathematically sufficient, since a tile is visited at most once or is discarded when already in the closed list. Insuffient space in the closed list is a strong indication of a broken implementation.
EDIT: I just checked it. It will work unless the value in simuconf.tab is too small (this value was for reducing the memory footprint and increase route search speed). DEBUG_ROUTE show that the way search from standard does not touch much more than 1/3 or all tiles even for very hidden ports back on two islands, even on large maps.
If route searching has to traverse the world fully at one level, let alone many, it's a strange map indeed.