One of the later challenges in Megaman Star Force 2 is the Bermuda maze: a fog-filled maze where each room had four exits, but only by going through the correct exit can the player advance. This kind of maze, where the player has to follow a specific route to pass through a repeating maze, has been around since the Lost Woods maze in the original Legend of Zelda on the NES. It remains a very popular kind of puzzle, having appeared in numerous games, such as Devil May Cry 1 and 3, numerous Zelda titles, Brave Fencer Musashi, and many more. It is an iconic kind of obstacle that has a lot of advantages and gives game designers a lot of options to play with.
It is a really interesting kind of maze since it is nearly impossible for the player to guess his way through. Most of these mazes are created by simply warping the player back into the same room he just exited, so it is impossible to tell if you are making progress or not until you either stumble back outside or find your way to the exit. So, a Lost Woods style maze is really more of a puzzle than a true maze, since the game designer needs to give the player some kind of clue in order to pass through the maze. Because of that feature, this kind of maze can also function as a good way to limit the player's access to an area until the story has progressed to a certain point.
One way of handling a lost woods maze is to make it unsolvable until the player is given a solution at one point. For example, the original Lost Woods could only be passed through by going North, West, South, and then finally West again. The instructions are given to the player by an old man hiding out in one of the dungeons. As a functionally identical alternative to giving the player a set of directions, some games give the player an NPC (often an animal) to act as a guide through the repeating maze.
The problem with this kind of maze is that it can be bothersome having to remember the instructions every time you pass through the maze, particularly if the maze blacks access to commonly visited areas. However, this can be made less bothersome if you make the solution fairly simple. A good example can be found in the Mu branch of the Bermuda Maze in Megaman Star Force 2. When it was time to first take that path, I was given straightforward instructions on how to get through: up right, down right, down left, up right, up left. I thought that it was going to be pain to remember those instructions, but then my brother pointed out that the instructions masked a simple solution: all I had to do was turn right at every intersection in the maze. That made passing through the Bermuda Maze a very simple process on subsequent passes.
The second common way of handling a Lost Woods style maze is to build a clue into the maze itself. A good example can be found in the Room of Rites, found at the end of both Oracle Legend of Zelda games. In this maze, there are eight or so statues, whose eyes will point in random directions every time the player enters the room. If the player is just entering or on the right path, none of the eyes will point in the direction of the correct path. However, if the player wanders off the correct route, the eyes will randomly point in all four direction. By looking for this behavior, the player can find his way to the exit. Personally, I prefer this kind of Lost Woods maze, since it is much more mentally engaging than just following a list of directions.
A major pitfall to this second kind of Lost Woods maze is that the clue needs to be possible to figure out (a common problem of puzzles I mentioned before). In Lunar Silver Star Story Complete for the PSX, there is dungeon called Myght's tower that had a Lost Woods maze. At one point the player is dumped into a room with four exits, each of which is marked with a distinct symbol (sun moon, star, planet). As far as I know, there are no clues past those symbols. I ended up getting lucky and stumbling through the maze by moving randomly. A lack of solid clues like that can bring a game to screeching halt, leaving the player to run to GameFAQs in order to progress.
A particular feature of Lost Woods mazes that I haven't mentioned is that they can easily lead to more than one destination if the player follows an alternate route. This lets the developers get multiple challenges out of a single maze, which can be very useful.
All told, I fully expect this kind of maze to show up in videogames for years and years to come. It is both very simple in concept, but allows for countless variations.