1. What NewGRFs are you using?
2. Are you using the OpenTTD supplied Finnish town name set?
3. Can you reproduce this with other OpenTTD-supplied town name sets?

1. No NewGRF
2. Game Options/Town Names/Finnish
3. Thousands of cities can be created with English and Czech city names, but with a Finnish set of only 327 cities. Normally, I don't use the Finnish name set. I ran into the problem by accident.

The problem was found in the discussion on the JGRPP version forum, but I found that the problem is not in JGRPP but in OpenTTD.

https://www.tt-forums.net/viewtopic.php?f=33&t=73469&start=2720

This problem exists with several of the town name generators, especially some NewGRF ones. Back when they were introduced, we had only 256x256 maps, which never had much more than 100 towns. but now we have 4kx4k maps which can easily fit 10k towns, and the town name generators run out of names.

unfortunately, we cannot really modify the town name generators, as that might break(*) old savegames.

(*) they could still be loaded, but the names will be diffferent, and duplicates may appear.

(Ignoring the savegame compatibility issue momentarily).

The Finnish town name tables and algorithm should support 780 names (which is better than 327 but still quite poor).
31 using "real" table.
27 using table 1.
722 using table 1/2 + table 3.

The use of SeedChance is such that which method to use and the indices into the various tables are linearly related due to use of overlapping or the same parts of the seed bits.
In general SeedChance and related methods are not a good way to extract bits from a random seed.

While it is entertaining to point out how bad the Finnish name generator is, as @Eddi-z pointed out, it was made back in the days when maps were smaller, and running out of unique town names was not an issue. And also it is not likely to be the only generator suffering from the same problem.

Additionally, at the time (~15 years ago) there was no specification as to how many unique names should a generator be able to produce. Is there such a specification even today?

Moreover, the fact that generators can never ever be modified due to save game compatibility is clearly a design flaw of OpenTTD itself, not of any particular generator.

Can we somehow keep the original (broken) Finnish generator around while also making an improved/fixed one? The original only gets used during savegame loading, to convert all town names into strings (as if they were renamed by the player) rather than the seed, and the new generator gets used for all new towns in old and new games.

Relevant: https://www.tt-forums.net/viewtopic.php?f=29&t=88477

The French town name generator is even worse, it's only 70 unique names.

Here are some possible solutions that would always work, but they might not be the prettiest:

1. When the town name generator runs out of names, start to generate fallback names (appending numbers to existing names, etc.)
2. Specify an optional fallback town name generator for all generators. If the generator runs out of names, switch to the fallback generator. If that one runs out as well, switch to the fallback of that generator. The default fallback town name generator is English.

Example for 2: If you selected Swiss town names, and run out, switch first to Austrian, then to German, then to English.

These solutions are not very pretty, but at least they guarantee that every town gets an unique name.

At the very least, a warning should be shown if the town name generator ran out of names.

Finally, I suggest a rule for official new town name generators. They should at least generate 5,000 unique names, and have been throughly tested before they find their way into the game. 5,000 because that's the current maximum of towns you can generate.

5,000 because that's the current maximum of towns you can generate

Actually, you can get way more than 5,000 towns. To verify, use the following map settings:

and start the game with the following Game Script (that prints the names of all towns, followed by how many towns there are):
Town Name Dump.zip

Example output (the final number at the end is the number of towns generated):

With this method, you can get somewhere between 11,000 - 13,000 towns in your game, instead of only 5,000, provided that your town name generator has enough names.