Okay, let's see if for Squeen's edification I can do a quick 'example of play' here. This is a summary of some travelling in about half a session in my home game.
Random encounters and most of the actual hex contents are omitted. This is just the back-and-forth of travelling through my hexmap.
The players are moving through dense jungle and can travel 2 hexes per day.
Day 1
Me: What's the plan for this session?
Players: We want to look for those ancient
burial mounds that the locals mentioned. We will head back to their camp and go on from there.
Me: Great. You head along the trail out of town [hex 0701, 0702] until you reach the cliffs [hex 0602]. Climbing down takes half the day, like usual. At the bottom, you enter the jungles. It is raining. I assume you are going your usual route. You reach the waterfall [hex 0703] by the time it gets dark. Everyone mark off a ration.
Day 2
Players: Let's follow the river to the goblin fort, then turn south.
[The group is navigating by familiar landmarks, since they are in dense jungle. Going along the river is quite handy.]
Me: Okay. You reach the goblin fort around midday. [Hex 0704] You don't see any patrols, and the rain makes it hard for the guards to spot you.
Players: Great, let's avoid these guys.
Me: You head south away from the river. [rolls for getting lost in the jungle away from landmarks, they are OK for now. Roll for discovery of hex contents, they found it!] Towards the end of the day, you come to an old Imperial watchtower built on low hill, crumbling and covered with vines. [hex 0604 - fight a giant locust, search the tower, find treasure and clues, etc]
Day 3
Players: Let's keep going this way to that old monolith we found before. From there, we'll turn east to find the wildmen.
[Because the group have been through these hexes a few times before, their chance to get lost is much lower when striking overland. Let nobody say I am without mercy.]
Me: Okay. Halfway through the day, you find the old monolith [hex 0505]. Turning east from there [rolls, another successful navigation check] you find the wildmen camp [hex 0506] at the end of the day. They are friendly since you helped them out last time. They offer you hospitality, so you don't need to mark off a ration today.
[Players hang out with the locals, blah blah]
Day 4
Players: Okay what did they say about these old mounds again?
Me: They point to the south and say they're about a day and some that way.
Players: Wicked, let's go.
Me: Okay, after a few hours you pass by the colourful stone towers you explored some time ago. [Hex 0405 - This is the extent of the group's exploration up until now. From here on, I roll regular chances to get lost] You travel on past them, progressing further south. The jungles here are a little less dense [hex 0306], but the terrain is still tough to get through and the rain shows no sign of slackening.
Day 5
Me: Continuing south. [They travel through hex 0206. They pass right by the burial mounds, which are in hex 0205. Oops!] You travel the jungle most of the day, and in late afternoon come across the crumbling remains of an old stone roadway, running east-to-west through the jungle. [hex 0106. Can't miss this as it runs across the whole hex]
Players: Okay, Leliana the witch is going to cast Wizard Mark on a piece of road so we can find this spot again. Now which way do we go? The wildmen didn't say anything about this. [debate debate] Let's keep going south, maybe it's further on.
Me: Okay, you travel a few hours more before nightfall [still in hex 0106]
Day 6
Me: Continuing south, the jungle is a bit less dense this way. The terrain is still rough and hilly, but the rain thins out some and you can see farther. [hex 0005 - Roll to get lost is easier. Hex contents are easy to see from anywhere in the hex anyway, no roll needed] After a few hours you spot a greenish-blue light in the sky like a spotlight on the clouds. It's ahead of you to the right.
Players: Weird! let's go towards it and check it out.
Me: Okay. You reach it around midday. A crumbling, ruined curtain wall surrounds a silver tower wrapped in a pillar of blue-green light. [describe the tower, the players go inside and immediately get scared]
Players: Fuck this! Let's get back to that crumbling roadway.
Me: Okay, you reach the road [hex 0106] by the end of the day.
Day 7
Players: [debate debate.] Let's follow the road west. Maybe we will reach the cliffs and get a sense of where we are.
Me: You guys follow the old roadway west. It isn't much easier to travel on this than through the jungle, it's so cracked and old. At least you can see a bit further. [no chance of getting lost. Pass through hex 0105]. In the late afternoon, as the roadway gradually ascends, the cliffs coalesce out of the mist and rain. The jungle thins out here [hex 0104] and gets more sickly-looking and dead the further you go. Finally, at the base of the cliffs, you come to a wide clearing, maybe 500 meters or so. Nothing grows here, and a low fog covers the ground. Up ahead is a great pit, and an earthen ramp leading to a cave entrance of some kind [Hex location 0104 - the road leads right to it].
Players: Oh boy...
Hexes are a tool that allows for placing locations and tracking player movements in a wilderness
to a playable level of accuracy. This is Dungeons & Dragons, not Compasses & Cartographers. The group is 'inside the hex' in a general sense. I don't have to know exactly WHERE unless they are at a particular keyed location.
These locations are also a little bit 'floating around in the hex,' because players can pass through a hex several times, even travelling the same route in the same direction without finding one. Common sense must be applied here (you have that, right?). If the goblin fort is built beside the river, the players will automatically discover it travelling along the river. For the watchtower in the middle of an overgrown jungle, the players could (and did) travel through that hex many times before stumbling across it. An understanding of your terrain and sight distances are obviously vital here. This trip would have looked completely different if the PCs were marching through amber waves of grain.
Hexes allow for simplicity, ease of use and crucially, a low cognitive load on the DM.
They
don't interfere at all with the players' sense of seamless exploration and travel.
There is no "mini-game."
There is no randomness - all these locations are either modules or my own creations, placed on the map long before the players got there.
You are objecting to problems that don't exist.