diff --git a/src/linkgraph/linkgraph.h b/src/linkgraph/linkgraph.h
--- a/src/linkgraph/linkgraph.h
+++ b/src/linkgraph/linkgraph.h
@@ -446,7 +446,7 @@ public:
 	typedef SmallMatrix<BaseEdge> EdgeMatrix;
 
 	/** Minimum effective distance for timeout calculation. */
-	static const uint MIN_TIMEOUT_DISTANCE = 48;
+	static const uint MIN_TIMEOUT_DISTANCE = 32;
 
 	/** Minimum number of days between subsequent compressions of a LG. */
 	static const uint COMPRESSION_INTERVAL = 256;
diff --git a/src/station_cmd.cpp b/src/station_cmd.cpp
--- a/src/station_cmd.cpp
+++ b/src/station_cmd.cpp
@@ -3419,11 +3419,44 @@ void DeleteStaleLinks(Station *from)
 			assert(to->goods[c].node == it->first);
 			++it; // Do that before removing the edge. Anything else may crash.
 			assert(_date >= edge.LastUpdate());
-			uint timeout = LinkGraph::MIN_TIMEOUT_DISTANCE + (DistanceManhattan(from->xy, to->xy) >> 2);
+			uint timeout = LinkGraph::MIN_TIMEOUT_DISTANCE + (DistanceManhattan(from->xy, to->xy) >> 3);
 			if ((uint)(_date - edge.LastUpdate()) > timeout) {
-				node.RemoveEdge(to->goods[c].node);
-				ge.flows.DeleteFlows(to->index);
-				RerouteCargo(from, c, to->index, from->index);
+				/* Have all vehicles refresh their next hops before deciding to
+				 * remove the node. */
+				bool updated = false;
+				OrderList *l;
+				FOR_ALL_ORDER_LISTS(l) {
+					bool found_from = false;
+					bool found_to = false;
+					for (Order *order = l->GetFirstOrder(); order != NULL; order = order->next) {
+						if (!order->IsType(OT_GOTO_STATION) && !order->IsType(OT_IMPLICIT)) continue;
+						if (order->GetDestination() == from->index) {
+							found_from = true;
+							if (found_to) break;
+						} else if (order->GetDestination() == to->index) {
+							found_to = true;
+							if (found_from) break;
+						}
+					}
+					if (!found_to || !found_from) continue;
+					for (Vehicle *v = l->GetFirstSharedVehicle(); !updated && v != NULL; v = v->NextShared()) {
+						/* There is potential for optimization here:
+						 * - Usually consists of the same order list are the same. It's probably better to
+						 *   first check the first of each list, then the second of each list and so on.
+						 * - We could try to figure out if we've seen a consist with the same cargo on the
+						 *   same list already and if the consist can actually carry the cargo we're looking
+						 *   for. With conditional and refit orders this is not quite trivial, though. */
+						v->RefreshNextHopsStats();
+						if (edge.LastUpdate() == _date) updated = true;
+					}
+					if (updated) break;
+				}
+				if (!updated) {
+					/* If it's still considered dead remove it. */
+					node.RemoveEdge(to->goods[c].node);
+					ge.flows.DeleteFlows(to->index);
+					RerouteCargo(from, c, to->index, from->index);
+				}
 			} else if (edge.LastUnrestrictedUpdate() != INVALID_DATE && (uint)(_date - edge.LastUnrestrictedUpdate()) > timeout) {
 				edge.Restrict();
 				ge.flows.RestrictFlows(to->index);