I'm definitely trying to avoid the feeling of "fast-forward" overland travel. In my current Ice Age campaign, I make a point of putting lots of stuff into overland journeys - plenty of interesting encounters with oddball denizens of the lands the PCs travel through, some hostile and some not.
IMO, the key is to avoid the sense of a "random" encounter, i.e., some monsters that you just fight and move on. Instead, I try for encounters that have a sense of belonging where they are, and that give the PCs a feeling of progress when they overcome them. In many cases, the encounter adds a bit of lore to the campaign, a place or person the PCs can revisit later.
For instance, the PCs had to undertake a trek of a couple weeks across the tundra to a place called Skullcrown. On the way, they had the following encounters:
#1: Halfling Caravan. Coming down out of the mountains onto the tundra, they found an orc raiding party attacking a halfling trade caravan. They killed the orc leader and helped kill or drive off the rest. The halflings gave them some information about the tundra and what to expect, and let them buy some magic items (I don't have standard "magic item shops" in my campaigns, but sometimes merchants come through with stuff for trade).
#2: Fallen Bridge. The PCs came to a bridge across a deep gorge. The halflings had warned them about evil spirits in the gorge. Unfortunately, the bridge was broken and they had to find a way across. In the process, they fought some wraiths and got hold of a magic dagger.
#3: Old Uncle. After the gorge, they came to Lake Winternight, where a peculiar fellow known as Old Uncle lived. The halflings had told them about him too, and his odd rules; no one was allowed to bring water into his tower, visitors weren't allowed to ask his name, and everyone had to shed three drops of blood on the threshold before coming in.
Getting Old Uncle to tell them about the road north and the lands around Skullcrown was a skill challenge. In the process, the PCs learned that Old Uncle was deathly afraid of "Them," beings from the lake. His rules were because of Them. They need the lake water to survive, so he doesn't allow water to be brought into the tower (he keeps a cistern to catch rain water). They have black blood, so visitors have to drip blood on the threshold to prove it's red. And if They ever learn Old Uncle's name, They can turn him into one of Them.
(When the PCs asked why he stayed there, if he was so scared, his reply was, "Someone's got to keep an eye on Them, or who knows what They might do?")
#4: Them. One of the things the PCs could do to get Old Uncle to help them was agree to get fish from the lake. He loved fish, but he was terrified of meeting Them by the shore. So the PCs went down to the lake. There they fought a couple of Them, and discovered They were aboleth servitors. They even spotted the aboleth itself for a moment, though they didn't fight it (they were only level 2 or 3 at the time).
#5: Wolves in the Snow. A blizzard hit the PCs, and then they were attacked by a pack of wolves. The wolves attacked in waves, getting beaten back and then returning in greater numbers. The third wave was led by a demonic wolf with glowing red eyes. After its death, a black shape like smoke billowed up out of it and fled. This would later prove to be a demonic agent of the main villain.
#6: Throog. The PCs came upon an ogre herdsman tending a herd of reindeer. He was friendly, if not very bright, and tried to recruit the PCs into his "herd." They managed to talk and trick their way past him (a skill challenge), but everybody loved the guy, and they later got him to help when they were being chased by an army on the way back.
#7: Ruined Shrine. This was an old shrine with the statue of a knight, Lord Imrahar, with his foot on the neck of a vulture-demon. Beneath the shrine was a crypt with a prophecy about the Lord of Vultures. The PCs were attacked in the shrine by an orc war-leader (plot-related); the statue of the knight helped them in the battle by stunning the orcs as they charged in. The PCs were unable to figure out the prophecy - not surprising, since I put it there as a possible hook for a future plot arc - and moved on.
So, by the end of this, the PCs were on friendly terms with two tundra-dwellers (Old Uncle and Throog), not to mention a halfling trade caravan. They had discovered a shrine with an interesting prophecy in it and some holy power associated with it. They had discovered an aboleth's lair and met a plot-related demon.
All this, I felt, made the trip a lot more interesting than just, "Let's see... okay, says on the wilderness encounters table you fight a bear." Of course, it did require having a fairly well-scripted route. Trying to put that same level of detail into a "hexploration" scenario could be pretty challenging.