And just as you said survival aspects such as need to food, water and sleep should slowly build up. Need for water should be stronger in hot regions, need for food bigger in cold regions.
I personally still don't see the problem wiht the quest compass, it needs some tweaking but the compass ITSELF is not bad.
May be a bit of self advertising and dunno if you read it but what do you think about http://www.gamesas.com/bgsforums/index.php?s=&showtopic=1044483&view=findpost&p=15187288
I'm working on a overworked version of that with some things rewritten and explained better but i think that's a good outline of the idea, it's pretty much "narrowing it down" instead of plain out pointing to your target location.
On other things, in Fallout it kinda makes sense your map doesnt show anything since the last time that map was updated in game was 250 years ago and, well, there was a nuclear war in between, so it's bound that nobody knows where new sttlements will be. In Oblivion those towns are around for hundreds if not thousands of years already.
I'd start out with a completely empty map that gets more and more detailed the further you explore it, kinda like you really start out witha blank piece of paper you slowly fill out instead of an actual map.
Yes, I'm all about the blank map concept, and I'm also ok with a compass as long as it's there to help you navigate and not just show you exactly where to go. I like the concept of having objectives narrowed down for the player character through conversation and research, rather than just a map marker appearing without any effort on the players part.