Firstly, on the "difficulty" of programming a teleport routine:
Teleporting an NPC when it gets stuck is actually a relatively straight-forward task to achieve. Identifying when an NPC has gotten caught is simple: you can calculate the Euclidian distance between the NPC and the player, and if it exceeds some threshold X, then you conclude that the NPC has gotten stuck and needs to be teleported back to the player. (Though it may be the case that the NPC is lagging behind, rather than trapped.)
Finding a suitable place to teleport the NPC to is a little more complicated to do - you don't want to teleport them into a wall, after all. Though I have no direct experience of this style of programming, I anticipate that it could be done by a combination of using the player's current location and orientation, adding an offset so they spawn behind the player, and using the game's existing clipping algorithms to ensure that the NPC isn't "out-of-bounds" relative to the player's position.
You might choose to zone particular areas of the map as being unsuitable for teleporting into, or alternatively use a whitelist of "safe" locations to teleport the NPCs to, and let them catch up with the player from the last teleport location they passed.
On why NPCs would get stuck in the first place:
The example you mentioned (Breath of Fire) has two NPCs following the player. These NPCs can't occupy the same space at the same time - not if we're aiming for realistic gameplay. And while you could write a pathfinding algorithm for the "permanent" structure of the level (rooms, corridors, etc), it wouldn't include moving objects that the NPCs would encounter.
The designers will have written some rudimentary AI to stop one NPC constantly trying to run through the leading NPC in an attempt to catch up with the player. In a game like GoldenEye for the Nintendo 64, where there are numerous NPCs, you could have two that each want to be where the other is stood (or somewhere beyond), and just try running through each other - at least until James Bond opens the door and shoots them both! That sort of unnatural movement and behaviour would break the player's suspension of disbelief.
Instead, when an NPC finds an obstacle between them and their immediate objective, they're programmed to respond in a slightly more realistic manner. An example would be for the NPC to turn slightly to the left, and try again to find a path to their objective. In the scenario of the two NPCs facing each other, if they both turn to their left they'll get out of each others' way, and can continue to their objective. These same collision avoidance routines are typically used for NPCs that are part of the player's party, too. Why reinvent the wheel, after all?
This illustrates how NPCs can stray "off the beaten path" that the player takes, in an attempt to respond to their environment in a realistic manner. Other ways they could get "caught up" or delayed when following the player include if their "hitbox" (which dictates whether they can stand on a ledge, fit through a gap, or be hit by a bullet) differs to that of the player, or if there are doors or platforms that operate on a cycle.
On the limitations of pathfinding algorithms for NPCs
While it is possible to calculate the shortest path for an NPC to take to catch up with the player, such calculations are not "free" - they have to compete for CPU time with everything else the games console is doing, such as rendering graphics, responding to user input, and calculating actions for all the other NPCs in the level too. Consider also the fact that these routeing calculations need to be updated as the player moves through the level. Spending ever more processing power on NPC AI would have diminishing returns beyond some given point, and with the limited power of early 3D consoles such as the Playstation and N64, you will reach that threshold sooner rather than later.
Even if you manage to route your NPC out of their trap, they can still end up lagging behind the player. If the player notices, and they want the benefit of having their party members alongside to help them through the level, they'll either have to stop and wait for the NPC to catch up, or (if they're still stuck) double back and go find them.
Encouraging the player to do either of those actions will break the flow of their gameplay, and probably leave them cursing the stupid NPCs for getting lost again. It is a more enjoyable experience if the game can make up for its technological shortcomings by teleporting NPCs back to the player. Ideally, if they reappear outside of the player's field of view, they might never know what happened!
