I remember playing 1st person shooter, Zero Tolerance, on Sega. I was covering that part of TV, which had map, with piece of paper, as it was defeating the sense of exploration, showing place, where I've never been. But I am also such person, that I can be put in middle of any dungeon in the game I played, and I will find my way out without any use of map.
Total lack of automap is bad, but Elminage provides it. It provides Magic Map (and later - its multi-use upgrade) and Save/Reload mechanism if you don't like 1-time maps. It provides spell Dioseed to see the map. You don't have to always have map at your eyes.
Focus on story at a cost of gameplay became disturbing at the end of 90s. Story is fine but it isn't CRPG-defining element. As Carmak said: "Story in a game is like a story in a porn movie. It's expected to be there , but it's not that important." Story is mandatory element of visual games and non-combat adventure games. I am glad we got some games recently, which have more focus on gameplay. Last good PC dungeon crawler was Demise, and it certainly was Demise of PC dungeon crawlers up until Elminage Gothic port (I don't count real-time games with engine exploits and MM X failed all expectations).
Sometimes I feel envy to console gamers (especially in Japan): they have 5 Elminage games, 3 Class of Heroes games, 4 (5 already?) Etrian Odyssey games, Unchained Blades, etc., etc., while PC gamers got nothing for over decade and I can see why. For some reason reception of such games on PC is bad. When you look on most of so-called CRPGs nowadays, they have automaps for linear dungeons and twitch-based gameplay, sadly it looks to be more popular than actual dungeons, where you can actually get lost, and where combat outcome is based on your characters' skills/stats and not on your dexterity skills.
dtgreene: I should also point out that many old first person RPGs lacked a map system, and yet people have still managed to beat them. Remember, you can draw your own maps on graph paper (and people actually did that back in the day).
Graph paper maps, pffft, I have all maps in my head :P
Edit: How is Lords of Xulima progress going?:)