The important thing about a map is not how complex it is, but how suitable it is for the setting and the purpose. A map of a natural limestone cavern, for example, is necessarily extremely complex; if it isn't, you don't have the sense of being in a natural space.
In the absence of one of those players who takes Profession: Surveyor and insists on lugging theodolites and levels around, the DM's job is not to enable accurate and precise map drawing, but to give the players a realistic sense of what their characters experience. As long as you bear in mind the limitations of the light sources, normal sight distance, and the special abilities of the party members (such as dwarfen stonesense), no map that is laid out along logical principles should be particularly tough to describe in play. It is important (as I learned the first time I ran a module - Sunless Citadel, obviously inspired by a trip to Winchester House!) to trace out routes through a map and make sure that they gibe with the setting's premise. Would the king/mad wizard/frontier baron/Peloran monks who built the structure have found that the map features suited their purposes? Do caverns form in this way? Then you're set. Usually when setting up a battle mat you don't have to put in every little irregularity, just enough structural features for the players to see their strategic options within a limited space.
For the players trying to stay oriented, there's nothing wrong with a schematic map composed primarily of labels joined by lines and squiggles on occasions when straightforward grid mapping becomes impractical. Turn over the mapping chores to the grognard with the text adventure experience at the table, and you'll find that it works fine.
BTW (archeology geek thread drift warning): Zigzag patterns incised on stone are among the most common and ancient motifs in human art. When I say ancient, I'm talking the Pleistocene - Egypt, eat your heart out. Nobody knows what they mean, but an archeologist told me, half-seriously, that he pictured people using these stones in the same way that modern people use maps drawn on napkins. These maps are not intended as precise depictions of the terrain, but as a mneumonic for verbal directions - "Okay, you go down here past the second stop sign and turn left, then right again at the pig sign and go on for a ways until you get to the bank of mailboxes and it's the second driveway past that on the opposite side of the road. If you get to the creek, you've gone too far."
PC maps are far more likely to resemble napkin (or incised stone) maps than they are grid reference maps.
Who did anyway?
