For, say, Oblivion, it would only show you the general region unless you're in it (say, Colovian Highlands would be highlighted until you enter it). Then the Highlands could be subdivided, and one of those areas could be highlighted. Then it finally goes active within, say, an arrow flight, and shows you the actual door/cave/person.
Then make this selectable at run-time.
In doors, the less helpful one would point to ALL exits to the current level that stay in the ruins until you've explored more. Fully explored floors then indicate the best route known to get to unexplored territory. Although quick exits could impair this... but there could be a workaround for that, too.
That way, when someone sends you somewhere, you can actually get a description, and the map shows you how to follow those... sort of. Additionally, it opens the door to telling yopu to find Dungeon 14 in Region 7. But you only know the region. You can go to towns there and get hints that narrow it down (ie, "Never heard of it, and I know every cave in the Northeast of this area" = de-select the north east cells of the region on the map)