Over on Paul's Gameblog, Paul is discussion mapping. I describe my method a bit in the comments.
It's worked pretty well in our games. As long as players don't worry too much about precision, or about trying to make their map and my map identical, it's not a big deal. It's still part of the challenge in my games. That's an important point - I'm not trying to make mapping as a challenge go away. We've had a lot of fun as a result of paper mapping.
But equally important is that I don't put in challenges that depend on finding every single square on the map. My maps look more like snaking tunnels through large areas of closed-off solid space than thin walls between rooms covering a whole sheet of paper. You are more likely to find a secret door with a good Search roll or Tracking roll or logical deduction than by mapping so precisely that "this one wall doesn't quite line up over here . . . there must be a hidden room!"
We do still struggle with caverns, and I may need a scaled-up visual layout of caverns to reveal to players as they go. Scaled-up because I do my maps small and the scale often varies. I need something consistent and easy. The easy is the hard part - I hand-drew a lot of maps, I can't scale them all up (some are on 11 x 17 already), and I really don't want to have to re-create my whole dungeon. We'll see what I end up with. Maybe I'll need to need to just sit down and do work to make less work for my players.