I've realized that I was spending as much time focusing on the map as on the environment, and exploring was more a matter of steering the arrow towards the blank spaces on the map than it was trying to keep track of paths and landmarks.
And the element of surprise was lessened by the fact that monsters invariably pop up when you enter unmapped territory. Now I'm not quite as sure whether I'm in a safe zone or not., so I'm a bit more alert.
With the map off the whole thing just feels a lot more immersive, which for me more than makes up for some time spent wandering around and retracing my steps.
Makes me think that my ideal setup for a game like this would be a an automap that you can only look at when not moving.
(Now if there were only some way of removing the stars for quest objectives from the map, I'd be really happy.)