Static maps for roguelikes can and HAS been done already. So you aren't in new territory! In fact, static QUESTS in roguelikes have been done too. Go play Tales of Maj'eyal if you haven't already. It is a shining beacon of roguelike + static elements = fun game. http://te4.org/

Thanks! I'll look into it.

Maybe the story could play off the fact that you're learning about the world and the people in it with each play through. Restarting from the same starting point over and over like groundhog day, or majoras mask.

The story is actually quite different. I'm going for something like Sword Art Online, where there is a machine capable of full dive virtual game system. The logic behind the permadeath fits perfectly, since my game world states that if you die in the virtual world, the data contained in that world is corrupted and disappears. Therefore, you need to restart from the scratch.