I was just pondering this the other day. There is an old adventure I once ran that has a great maze in it, but playing it out as a mapping exercise made it rather un-fun. I've been wanting to run that adventure again, and I've been thinking of ways to make the maze part as much fun as it deserves. The solution I came up with is only good if:
- you're okay with managing the maze descriptively
- you using a system that allows for skill checks or conflict tests
- there are hazards in the maze that could be blundered into or avoided
The overall concept is to describe the twistings and turnings of the maze as the characters navigate it, but not have the players try to navigate it. Instead, have them roll an appropriate skill or conflict to navigate the maze "safely". On a failure, continue the description of the maze at one of the hazard locations, just as if the PCs had walked into an encounter room.
Once they deal with the hazard and move on (or if they succeeded on the original check to avoid the hazard) describe them coming to a part of the maze that's definitely new to give the players a sense of progress through the labyrinth.
Continue like this until they've either avoided or met each of the hazards. Should the players run into a hazard and decide to backtrack to try to go around, let them, but keep describing them running into the hazard—they failed the check, so they have to face the hazard to make progress in the maze. (Of course, if they're really clever, make exceptions to this as you like.)
There are games with subsystems already well-suited to this. Skill Challenges in D&D 4th edition are nearly perfect. Games like Burning Wheel that use conflict resolution are well-suited to running this kind of structured challenge on-the-fly as well, if you make avoiding or encountering each hazard the point of the conflict roll.
Exemplis gratis
Take for example a simple maze with one monster and three pit traps. The spots where the pit traps are concealed are particularly narrow, short, straight corridors in the maze. The spot where the monster resides is a moderately-sized room after a few quick bends, so the PCs will come into the room suddenly without warning. (This "can't avoid the room" setup for the hazards is optional, but will make it smoother to run, as the players can't try to game the overall challenge by falling back to the "map it all and creep around" kind of play that you're trying to avoid.)
The PCs make a check or contest roll to navigate the maze. You don't need to announce the success or failure, but it depends on your play style whether you want to tell the PCs that the consequence of the roll is encountering a hazard, or whether you want to just let them discover that they're in trouble as you keep describing their movement through the maze.
Let's assume a success. Reward the players with description that sounds like they're making progress: turns they don't recognise, incidental features and dungeon dressing that they've haven't seen before, or a sense of direction telling them that they've managed to leave behind the last section of the maze.
Mark off one of the hazards, such as one of the pit traps. They've avoided that part of the maze and won't need to go there to find the exit.
Next roll, they fail. Describe the same sense of moving forward, but then bring your description to a narrow "action" focus as they come to the corridor with the pit trap. Call for agility rolls, saving throws, or whatever is appropriate. They'll deal with the trap, suffering more or less.
Next roll, they fail again. The last pit trap is ahead of them and they need to get past it. If the players recognise the setup, that's fine: let them approach cautiously, applying what they learned last time. Maybe they figure out where the trap is and all jump over it, or lay two poles across it and walk over those. Generally, let them be clever and enjoy outsmarting the trap—and if they're not clever, it'll run just like the first time. Either way they have to deal with it, and it will be interesting.
That makes three rolls out of four hazards. The final roll will determine whether they stumble into the monster's lair within the maze, or whether they manage to find a clear way past it. If they succeed you can describe the sounds of the monster just behind the wall, then dropping behind them as they see the exit. If they fail, you get an interesting fight, then they quickly find the exit.