RCT and other Chris Sawyer games would be an excellent example for a case study. They are both a product of the limitations of their time as well as Chris Sawyers self-chosen handicap of writing the entire game in assembly.
In addition, the source code for both RollerCoaster Tycoon and Transport Tycoon Deluxe have been decompiled by volunteers and released as OpenRCT2 and OpenTTD respectively. So we can actually get a glimpse at how the games worked originally.
Disclaimer: I am not an expert in both of these games, and the following examples may be wrong. In any case, you can just take these as hypothetical made-up examples.
As far as I remember, both games have a very fast heuristic for wayfinding.
In RCT the agents ("peeps") just wander most of the time (at the very least 50%) and just pick a path at random at each intersection. This is obviously very cheap even for many agents. Peeps also have the possibility to seek out an actual goal (like a specific ride in your park), but even then peeps do not employ global pathfinding to reach that target, but again they just check at each intersection which path would lead them closest to their target and move there.
This works well in most cases. But it is well-known to RCT players that certain patterns of paths can lead to peeps getting stuck in cycles when the heuristic fails. In addition, at least in RCT1, for that reason double paths were completely broken, as every path segment is an intersection and it becomes evident that peeps wander completely aimlessly.
The thing is: Players usually see this as a challenge rather than an annoyance. The game design even incorporates this, for example by giving you a negative "award" for a "confusing park layout", or scenarios which are built around the gimmick that the pre-existing path layout in the scenario is actively horrible and should be reworked asap. The problems of double paths actually make the game better as those are a naive and overly cheap solution for overcrowding (another mechanic which penalizes you for having to many peeps on a stretch of path at the same time.)
Another example of technical limitations turning into important gameplay elements can be seen e.g. in Starcraft. Only being able to select 12 units at the same time, and having wonky pathfinding, especially in chokepoints, is completely outdated. Still, having to deal with these limitations is actually considered part of required skill in high-level play.
In addition, some of these limitations are actually realistic, as people in a real amusement park will not have a perfect map of the park in their heads and just wander around like the peeps do. In game you also have the possibility to sell park maps, which are consulted by the peeps when they look for something. Theoretically, even if the game had implemented a perfect pathfinding algorithm, you could still cut down on the opportunities where you need to run that algorithm by tuning how often the peeps will check that map. Peeps also have a mechanic where they have a "favorite ride" which they seem to visit all the time. When they stay in close vicinity of the ride, even targetted pathfinding gets very easy.
Transport Tycoon actually had pretty much the same pathfinding algorithm as RCT. One of the first things that OpenTTD did was reworking the pathfinding. As you are building a railway network in that game, splitting the network into an actual graph, keeping that structure in memory, and running A* or something on it, is actually not that inefficient.
It seems that it would have been possible even on slower PCs, but remember that Chris Sawyer wrote the game in assembly, and having a simple pathfinding algorithm actually really helps managing the complexity. After decompiling to a higher-level language like C++, resolving these issues became much easier.
I also remember playing The Settlers 2 a lot as a kid. This game had a weird mechanic where you had to place flags on the map and you built paths between each of those flags. Each of those path segments would then be manned by one of your infinite supply of basic settlers. Those settlers would never leave the path, instead just carry items from one flag to the other, handing it off to the next settler. I have never found an explanation for this design decision, but I am pretty sure that the reason is that you don't have to induce a graph into your roadway system as the player is pretty much building the graph of the road network themselves.