Mapping is not that damned hard. A player should know where his character is on the grid. If not, either the DM is describing it damned poorly, or the player is a complete dink.
Complex mazes? Sure, make the character invest some time. But much of it should fall under a basic INT test. Sit yourself down, and draw a basic map of how you get to *some generic place* everyday. It ain't rocket science, it doesn't have to be done on the fly, and it doesn't have to be done at the moment you are there.
Memory is a marvelous thing. I have no skills invested in Survival IRL but I can tell true north most days, and I can navigate most cities and find my way back out, without a map. Why shouldn't our characters?
Now, in the first scenario I described in my previous post, none of the characters had any Craft:Cartography skills, but we could get around the world, and around a dungeon, regardless of my abilty to visualize things. Hence the "dirt map". My new char DOES have Craft:Cartography. Are you seriously suggesting that half his day should be spent out of action, drawing rinky-dink dragons and narwhals and mermaids on a piece of parchment?