Tsunami,
Fantastic idea, I'm stealing it too.
Something I haven't done in a while is to make a dungeon that contains a few of easy mazes, say 2 or 3. If you follow the right wall, or the left wall, the maze is easily solved. throw in some minor traps, or encounters, easy puzzles or someting along those lines. Then throw in a fake maze. if you follow the right or left wall, it just takes you around in a circle back to the entrance. of course there are traps at odd intervals along that outside wall. If you just go straight 40 feet and turn right there is a short hallway with stairs that lead out of the maze.
The trick is to convince the players that they are brilliant for having solved the first mazes so easily. That last maze should be a real surprise.
In the past I've usually run mazes by simply asking what characters strategy was and then running the important parts, but I like tsunami's idea, and I'll give it a shot.
Chris