Hic Sunt Dracones. Terra Incognita.
Certain knowledge is an enemy of wonder. We frequently see advice on begetting uncertainty through monster usage; use a custom bestiary, or mix up the characteristics of monsters to keep the players on their toes. For me the problem goes further - the very act of creating statistics to define a thing limits the possibilities by bounding them. I consider this a curse of Westernism, and blame Aristotle. This is not escapable on the DM's side of the screen; to define a thing is to reduce it, and as game masters, this is what we do.
But today I'm considering a complimentary topic, regarding the hex map; as modern people, we take for granted that maps are accurate.
Where do fairy tales take place? It's always "once upon a time in a land far, far away", an indeterminate period in an indeterminate kingdom - the tales can be anywhere in Europe, but left to the reader's imagination. The great 1930's horror movies I like so much are vaguely placed in central Europe or Germany, someplace east of the Alps but west of Russia - a foggy land of pre-modern technologies and lonely castles and superstitious peasants you also won't find on any maps.
As the game master, you need to know the monster statistics, just as you need a firm grasp of the geography of the game world. A map is an awfully convenient way to organize information, after all. But the intent behind custom bestiaries is to keep that sense of discovery and unknown in the encounter system; can't we do a similar situation with our maps and exploration?
I've never placed a high premium on wilderness maps for the players that deviate from the game master's map, but my opinion is clearly changing. Sure, I've used the simple approach of leaving white space, but for a scrawled warning of "beyond here, there be monsters" or "unknown lands". How about distortion of scale or coastlines, the way old maps of the globe show a clearly defined Europe, but vague outlines for the New World continents?
Another approach is presenting the map like old street directions. For instance, I really liked a Salisbury player's map I saw in Pendragon; it was an abstract collection of heraldic devices, landmarks, and walking distances, delineating the extent of player knowledge through areas known via oral tradition. I could see a similar approach in a nautical campaign where the "map" consists of sailing directions and distances.
What it comes down to is appropriately defining the well-known local world of the players, while keeping the larger world vague or incorrectly described to reinforce the thrill of exploration and wonder. A nice side effect is that maps of far off places become a much more important source of treasure. Englishmen in the Age of Sail were knighted for returning home with maps and charts taken from the experienced navigators of the Spanish or Portuguese. The value of a good map is apparent if you're going to travel off the edge of the world.