diff --git a/docs/landscape.html b/docs/landscape.html
--- a/docs/landscape.html
+++ b/docs/landscape.html
@@ -513,7 +513,7 @@
    <td valign=top nowrap>&nbsp;</td>
    <td>
     <ul>
-     <li>m2: Index into the array of towns (owning town for town roads; closest town otherwise, INVALID_TOWN if not yet calculated)</li>
+     <li>m2: Index into the array of towns (owning town for town roads; closest town otherwise, INVALID_TOWN if there is no town or we are creating a town)</li>
      <li>m3 bit 7 set = on snow or desert</li>
      <li>m7 bits 7..5: present road types
       <table>
diff --git a/src/openttd.cpp b/src/openttd.cpp
--- a/src/openttd.cpp
+++ b/src/openttd.cpp
@@ -2563,7 +2563,7 @@ bool AfterLoadGame()
 
 	if (CheckSavegameVersion(103)) {
 		/* Non-town-owned roads now store the closest town */
-		InvalidateTownForRoadTile();
+		UpdateNearestTownForRoadTiles(false);
 
 		/* signs with invalid owner left from older savegames */
 		Sign *si;
diff --git a/src/road_cmd.cpp b/src/road_cmd.cpp
--- a/src/road_cmd.cpp
+++ b/src/road_cmd.cpp
@@ -319,9 +319,9 @@ static CommandCost RemoveRoad(TileIndex 
 						DoClearSquare(tile);
 					} else {
 						if (rt == ROADTYPE_ROAD && IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN)) {
-							/* Promote ownership from tram or highway and invalidate town index */
-							SetRoadOwner(tile, ROADTYPE_ROAD, GetRoadOwner(tile, (HasBit(rts, ROADTYPE_TRAM) ? ROADTYPE_TRAM : ROADTYPE_HWAY)));
-							SetTownIndex(tile, (TownID)INVALID_TOWN);
+							/* Update nearest-town index */
+							const Town *town = CalcClosestTownFromTile(tile, UINT_MAX);
+							SetTownIndex(tile, town == NULL ? (TownID)INVALID_TOWN : town->index);
 						}
 						SetRoadBits(tile, ROAD_NONE, rt);
 						SetRoadTypes(tile, rts);
@@ -348,7 +348,7 @@ static CommandCost RemoveRoad(TileIndex 
 			}
 
 			/* Don't allow road to be removed from the crossing when there is tram;
-			 * we can't draw the crossing without trambits ;) */
+			 * we can't draw the crossing without roadbits ;) */
 			if (rt == ROADTYPE_ROAD && HasTileRoadType(tile, ROADTYPE_TRAM) && (flags & DC_EXEC || crossing_check)) return CMD_ERROR;
 
 			if (flags & DC_EXEC) {
@@ -1274,14 +1274,22 @@ void DrawRoadDepotSprite(int x, int y, D
 	}
 }
 
-void InvalidateTownForRoadTile()
+/** Updates cached nearest town for all road tiles
+ * @param invalidate are we just invalidating cached data?
+ * @pre invalidate == true implies _generating_world == true
+ */
+void UpdateNearestTownForRoadTiles(bool invalidate)
 {
-	TileIndex map_size = MapSize();
+	assert(!invalidate || _generating_world);
 
-	for (TileIndex t = 0; t < map_size; t++) {
-		if (IsTileType(t, MP_ROAD) && GetRoadOwner(t, ROADTYPE_ROAD) != OWNER_TOWN) {
-			/* GetRoadOwner(t, ROADTYPE_ROAD) is valid for road tiles even when there is no road */
-			SetTownIndex(t, (TownID)INVALID_TOWN);
+	for (TileIndex t = 0; t < MapSize(); t++) {
+		if (IsTileType(t, MP_ROAD) && !HasTownOwnedRoad(t)) {
+			TownID tid = (TownID)INVALID_TOWN;
+			if (!invalidate) {
+				const Town *town = CalcClosestTownFromTile(t, UINT_MAX);
+				if (town != NULL) tid = town->index;
+			}
+			SetTownIndex(t, tid);
 		}
 	}
 }
diff --git a/src/road_cmd.h b/src/road_cmd.h
--- a/src/road_cmd.h
+++ b/src/road_cmd.h
@@ -8,6 +8,6 @@
 #include "direction_type.h"
 
 void DrawRoadDepotSprite(int x, int y, DiagDirection dir, RoadType rt);
-void InvalidateTownForRoadTile();
+void UpdateNearestTownForRoadTiles(bool invalidate);
 
 #endif /* ROAD_CMD_H */
diff --git a/src/road_map.h b/src/road_map.h
--- a/src/road_map.h
+++ b/src/road_map.h
@@ -189,10 +189,21 @@ static inline void SetRoadOwner(TileInde
 
 static inline bool IsRoadOwner(TileIndex t, RoadType rt, Owner o)
 {
-	assert(rt == ROADTYPE_ROAD || HasTileRoadType(t, rt));
+	assert(HasTileRoadType(t, rt));
 	return (GetRoadOwner(t, rt) == o);
 }
 
+/** Checks if given tile has town owned road
+ * @param t tile to check
+ * @return true iff tile has road and the road is owned by a town
+ * @pre IsTileType(t, MP_ROAD)
+ */
+static inline bool HasTownOwnedRoad(TileIndex t)
+{
+	assert(IsTileType(t, MP_ROAD));
+	return HasTileRoadType(t, ROADTYPE_ROAD) && IsRoadOwner(t, ROADTYPE_ROAD, OWNER_TOWN);
+}
+
 /** Which directions are disallowed ? */
 enum DisallowedRoadDirections {
 	DRD_NONE,       ///< None of the directions are disallowed
diff --git a/src/town_cmd.cpp b/src/town_cmd.cpp
--- a/src/town_cmd.cpp
+++ b/src/town_cmd.cpp
@@ -94,12 +94,12 @@ Town::~Town()
 				break;
 
 			case MP_ROAD:
-				if (!IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN) && GetTownIndex(tile) == this->index) {
-					/* Town-owned roads get cleared soon, anyway */
-					SetTownIndex(tile, (TownID)INVALID_TOWN);
-					break;
+				/* Cached nearest town is updated later (after this town has been deleted) */
+				if (HasTownOwnedRoad(tile) && GetTownIndex(tile) == this->index) {
+					DoCommand(tile, 0, 0, DC_EXEC, CMD_LANDSCAPE_CLEAR);
 				}
-				/* Fall-through */
+				break;
+
 			case MP_TUNNELBRIDGE:
 				if (IsTileOwner(tile, OWNER_TOWN) &&
 						ClosestTownFromTile(tile, UINT_MAX) == this)
@@ -116,6 +116,8 @@ Town::~Town()
 	MarkWholeScreenDirty();
 
 	this->xy = 0;
+
+	UpdateNearestTownForRoadTiles(false);
 }
 
 /**
@@ -1564,8 +1566,9 @@ CommandCost CmdBuildTown(TileIndex tile,
 	if (flags & DC_EXEC) {
 		Town *t = new Town(tile);
 		_generating_world = true;
+		UpdateNearestTownForRoadTiles(true);
 		DoCreateTown(t, tile, townnameparts, (TownSizeMode)p2, p1);
-		InvalidateTownForRoadTile();
+		UpdateNearestTownForRoadTiles(false);
 		_generating_world = false;
 	}
 	return CommandCost();
@@ -2471,26 +2474,32 @@ Town *CalcClosestTownFromTile(TileIndex 
 
 Town *ClosestTownFromTile(TileIndex tile, uint threshold)
 {
-	if (IsTileType(tile, MP_HOUSE) || (
-				IsTileType(tile, MP_ROAD) && HasTileRoadType(tile, ROADTYPE_ROAD) &&
-				IsRoadOwner(tile, ROADTYPE_ROAD, OWNER_TOWN)
-			)) {
-		return GetTownByTile(tile);
-	} else if (IsTileType(tile, MP_ROAD)) {
-		TownID town_id = GetTownIndex(tile);
-		Town *town;
-
-		if (town_id == INVALID_TOWN) {
-			town = CalcClosestTownFromTile(tile, UINT_MAX);
-			if (town != NULL) SetTownIndex(tile, town->index);
-		} else {
-			town = GetTown(town_id);
-		}
-
-		if (town != NULL && town->IsValid() && DistanceManhattan(tile, town->xy) < threshold) return town;
-		return NULL;
-	} else {
-		return CalcClosestTownFromTile(tile, threshold);
+	switch (GetTileType(tile)) {
+		case MP_ROAD:
+			if (!HasTownOwnedRoad(tile)) {
+				TownID tid = GetTownIndex(tile);
+				if (tid == (TownID)INVALID_TOWN) {
+					/* in the case we are generating "many random towns", this value may be INVALID_TOWN */
+					if (_generating_world) CalcClosestTownFromTile(tile, threshold);
+					assert(GetNumTowns() == 0);
+					return NULL;
+				}
+
+				Town *town = GetTown(tid);
+				assert(town->IsValid());
+				assert(town == CalcClosestTownFromTile(tile, UINT_MAX));
+
+				if (DistanceManhattan(tile, town->xy) >= threshold) town = NULL;
+
+				return town;
+			}
+			/* FALL THROUGH */
+
+		case MP_HOUSE:
+			return GetTownByTile(tile);
+
+		default:
+			return CalcClosestTownFromTile(tile, threshold);
 	}
 }
 
diff --git a/src/town_gui.cpp b/src/town_gui.cpp
--- a/src/town_gui.cpp
+++ b/src/town_gui.cpp
@@ -725,14 +725,15 @@ public:
 
 				this->HandleButtonClick(TSEW_RANDOMTOWN);
 				_generating_world = true;
+				UpdateNearestTownForRoadTiles(true);
 				t = CreateRandomTown(20, mode, size);
+				UpdateNearestTownForRoadTiles(false);
 				_generating_world = false;
 
 				if (t == NULL) {
 					ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
 				} else {
 					ScrollMainWindowToTile(t->xy);
-					InvalidateTownForRoadTile();
 				}
 			} break;
 
@@ -740,11 +741,11 @@ public:
 				this->HandleButtonClick(TSEW_MANYRANDOMTOWNS);
 
 				_generating_world = true;
+				UpdateNearestTownForRoadTiles(true);
 				if (!GenerateTowns()) {
 					ShowErrorMessage(STR_NO_SPACE_FOR_TOWN, STR_CANNOT_GENERATE_TOWN, 0, 0);
-				} else {
-					InvalidateTownForRoadTile();
 				}
+				UpdateNearestTownForRoadTiles(false);
 				_generating_world = false;
 				break;