This is really a huge plot hole, because the Teleport System can only send someone to towns that they remember visiting. Of course, there's no mention of how someone is going to get to the other town to have a memory of visiting it!
Good question. I think it's hard to separate what actually is the story from the "in-game" details/optional difficulties. Probably in the real story this aspect would be scraped. Anyway, let me try:
Teleports not always existed in Motavia so, at some point, everyone had to walk to reach another town. Meanwhile they created teleport centers and, at that time, cents of people (at least) knew several towns... so if a friend of mine already been in Zema, I would be able to travel with him (even if I never had been there before)… in the beginning it would work as a trading card game where pokémons were Mota towns.
An example of this is that, in AW1284, if a member of Rolf's party had previously been in a town, all members of the group can go there without previously visiting it. We can also consider this "plot hole" to be another restriction (although implicit) of Mother Brain.