So it sounds like you want to add some thought, memorability and danger into the travel time, but you don't want them to meta-game things so that they are overpowered by the time they reach their destination. You don't want them 'hanging around' these locales longer than necessary, over-foresting the fiendish-squirrels to extinction for XP. I would handle this a couple of ways:

Low treasure for random encounters

If you award XP by the book, with no extra 'story point awards' and keep treasure low to Nil (sorry the Dire Lions did not drop 100gp and a pair of bracers +4), I don't think they'll stay there long or advance too quickly.

Keep the CR level of the encounters in the Yellow Zone

I would keep it maybe at or a tick or two 2 above the party level; whether from sheer numbers of opponents (a large # of giant ant warriors) or quality (1 hill giant) or circumstance (see weather below). I think that most wilderness encounters are things that players should at least think about avoiding or fleeing from. These are encounters that should bloody them if they take them head on.

Roll encounters 'randomly' in advance

Roll a few (2 or 3) wilderness encounters in advance and write the results down on notecards so you at least have some idea of what they are going to be ahead of time. Helps to think about 'if this goes down, here's how it will go down'. Then for the encounter check, you are rolling to see if the encounter occurs (not IF it occurs and WHAT it is; you already know what the WHAT will be. You can also determine the encounter distance in advance or things like that)

Roll the Weather in advance

If there is going to be a lot of overland travel time expected, actually roll the weather up for the next three months. This (can) add a lot of flavor to encounters that do happen. Fighting a Troll in the middle of rainy deluge (or even a dry spell where the whole forest is ready to go up like a matchbox) can be a whole different ballgame from what players are used to. A swarm of Gibberlings in dense fog banks could also be unnerving; it is the Wilderness, so play up the different conditions that can happen there.

Track player supplies, and make foraging a dangerous challenge

In many of the classic fantasy novels, starving or dying of thirst is a real problem. This gets overlooked too often I think, or just 'handled' by someone making a Survival check at +10 or the like. Set some higher DC levels for different areas for foraging. When foraging, check for random encounters. (you might not be the only predator tracking that wild boar...) If an area has a low forage yield, it may be inhospitable, or there may be a real 'top of the line' predator around causing the imbalance.

Use Stalking encounters

Quite a few monsters (natural and unnatural) tend to stalk their prey for quite some time and 'wear them down' preventing them from resting, picking off stragglers. Wolf packs, Meenlocks and many others might come to mind here. Being in the wilderness means there is no safety. You may know 'something' is out there, you might even skirmish it into a quick retreat, but that doesn't mean it isn't going to come back a little later. Stalking is probably waaay underutilized in the wilderness.

Make it a challenge for the characters to exist in the Wild, and they'll not only remember it, they may feel relieved to get to where they are going.

I see two primary ways to approach this, depending on the travel. (TL;DR at the end)

Travelling through civilized lands

From your description, it seems like your players (who are, considering you are playing D&D4e, are basically powerful heroes) are travelling between two cities in a civilized nation. In this case, I'm not even sure if I'd run any kind of straight forward combat encounter. After all; it's not much of a civilized country if random merchants have a high chance of bumping into something that's a threat even to a group of adventurers. They would be scared to travel that road, and with good reason.

Instead; make a list of random encounters that highlight the kind of things you would expect to see on such a road. These can be short (like a few minutes), focused on roleplaying, and highlight exactly the things that make this part of the world unique. They can be dangerous situations, but they should be dangerous for others and mostly resolved by talk. They can also simply be amusing, peculiar, atmosphere building, or setting up for later adventure.

Each should have one or more actors and a situation that is happening. (Those without actors other than the players are usually boring; those with actors but no situation are usually just ignored)

I don't know the setting you're using, but I'll try to make a list of the kinds of things you can run:

Generic Actor examples:

• A single traveling merchant with a backpack. Would most likely be a bit scared of meeting what looks like a warparty.
• A traveling caravan. Will have their own guards, might even sell the players some stuff. Probably cares something that is of no interest to them, like food, cloth, ore, etc.
• A noble party. Might be out hunting, might be on a diplomatic visit, might just be taking a stroll. Will have lots of money and gear, guards, servants, etc. Would probably be a little disdainful of the players.
• Hunters or farmers. Probably just out working, mostly disinterested. Or maybe just slacking off and caught in the act.
• A military patrol. These guys are the primary reason you don't get random encounters that involve very dangerous creatures. Will ask some questions about why an unafilliated group of heavily armed people are traveling the road, probably.
• Some form of wildlife. Could be a wolf, or a deer, or a group of rabbits. Will probably just be scared of the players and run away (yes, the wolf also)
• Bandits. Will probably not ambush the players because they are not suicidal, but might be seen in the bushes, or pop up only to realise their mistake and start running.
• A fellow wandering adventurer type. Might be a good one, might not be. Might just be a travelling bard or a local druid.

Next, come up with a suitable situation for them to be in. Maybe two of these groups have bumped into each other. Perhaps the nobles ran over one of the farmers, and now he's wounded. Maybe the military patrol is questioning and intimidating the lone merchant. Maybe a travelling cleric is annoying a hunting party. Maybe the bandits are ambushing someone just as the players approach.

Let them roleplay through a few of these simple situations, interspersed with "for a few days, nothing interesting happens.". This will give them an idea that things happen in your world; you get some chances to tell of the changing terrain (seeing more and more military patrols in these little encounters would reinforce the idea of heading into a dangerous or militant country, while meeting more travelling bards would give a very different kind of country)

(If you run something along the lines of "you find bandits ambushing a farmer", don't grab the dice. Run it more like either the players scaring off the bandits and the farmer thanking them, or a hostage situation. These bandits are no match for the players and they know it)

In addition; if you want to highlight the strain of long time travel with a bunch of quirky people (like most adventurers are), ask each of them beforehand to give you one description of something his character does during the trip (or does in general) and then for every long travel randomly pick one of these things and use them as a highlight in the travel.

If your party Elf has told you that he likes to sing during the journey, run one short encounter that starts with "Today has been calm. For the 10th day in a row, the Elf has spent most of the past 6 hours singing.", followed by a bit of silence. If the players care about interparty social interaction, they'll probably jump on that cue and have a few interactions. (If they don't care, they won't but you probably can't make them anyway)

The more of these short moments you have, the longer the trip feels. If the players are preparing for a long trip then you shouldn't feel bad spending an hour (or two) just doing a bunch of these. I've spent half of my last session mostly like this; just the players bumping into various characters from the region they were in.

If your players start getting bored, you can consider throwing in something with a little more threat but an easy option out, so the players can decide whether they want to pursue or not. Instead of having a Hydra come crashing onto the path, have someone bump into them and warn them that he's seen a Hydra in a nearby cave and that he's scared it'll attack a nearby village. It shows them the world can be dangerous, without being continuously attacked by things, and gives them the option to roleplay saying "no".

Travelling as an adventure

When a travel is through more of a wilderness area and for long duration, you should treat the voyage like an adventure in itself. Map out some things that are going to happen on the road (these don't even have to be random) and then see what the players do.

Make sure you spend some time at the start where the players prepare for their journey. Let them get some information about likely things to encounter (in terms of terrain, weather, villages, monsters, dungeons, etc) and give them time to prepare for these things. As they start on their journey, use short roleplaying encounters as described above as they set off, but alternate them more and more with encounters with more dangerous and uncivilized opponents. Their journey does not start in the wilderness most likely; so as they set out they will meet some merchants and workers, then at some point mostly military partols and some workes, then military patrols and the occasional savages/monsters, then at some point only wilderness encounters.

All of the wilderness encounters should still have a situation that doesn't immediately involve combat. Running into a party of Goblins that try to kill the players is a cliché, but running into a party of Goblins that are picking berries can also be very interesting (and quickly turn into the former if the players approach it wrong!)

When it comes to the players maybe facing something much more powerful, that's also a case of foreshadowing. The odds of two entities traveling a land to randomly run into each other is very small. However, if one of these two entities is trying to find the other, the chance goes up considerably. But that also means you might get early warnings. This is then the best way to set up the atmosphere for a "random" encounter.

Consider the following series of encounters:

• A group of Goblins hiding under a large plant. Some are scavenging mushrooms while others keep watch. They seem to have their eyes mostly on the sky. If the players try to talk, they get "shush"ed. If they try to speak softly and in Goblin, they get warned that there might be a Dragon in the area.
• The players see smoke up ahead. They come upon a clearing in the forest. All the trees in a 100ft area are smoldering, some plants and trees are still on fire.
• A massive shadow flies overhead. Looking up, the players see a huge creature going off into the distance, but it does not pay them any attention.
• The players come out to a slope down; no trees grow here and the path down looks treacherous. As they struggle their way down, somewhere ahead in the forest, not that far away, they see another pillar of black smoke coming up. (This will probably make them go "uh oh", but nothing else happens)
• The players come upon a small plain in the middle of the woods. Nothing to give them cover; but no real way around it. As they step out into the clearing, the Dragon they've heard of, seen overhead, and whose path of destruction they've witnessed slams down behind them and lets out a terrifying "FOUND YOU!" before opening its mouth.

The above is, ultimately, the same as just pitting the player against a Dragon in a featureless plane, except that now the atmosphere is set, the players get ample opportunity to come up with plans to avoid this Dragon, it doesn't feel random, the players will probably not go "oh a clearing, time for some random encounter" (even if they know exactly what is going to happen) and it'll feel like they've been travelling for quite a while.

Likewise, you can use weather effects without dice rolls if you make them a part of the story. Rather than saying "it rains, roll Endurance", you can simply make the observation "dark clouds gather overhead. you remember the warning the villagers gave you about how rain can keep coming for days on end." and go from there. If they decide to travel through it; tell them how they get chilled to the bone. Ask them how they'll deal with that. Only use dice when they keep ploughing on without taking any precautions. (And make those dice hurt)

Giving them foreshadowing, the option to adapt their plan, and letting them avoid much of the nastiness if they came prepared makes the world come alive. Having 3 short encounters where the rainfall is described as "continuous" makes it feel like the rain is really, really bad. Players will learn to measure travel by how many small things happen on the road, and anything that keeps happening during all of them will also start feeling really long.

Extended example from my last session

Setting

This took place as my players prepared to venture from their old city towards an ancient, abandoned temple to the dragon god of culture in the hopes of fixing their dead friend. They knew very little of the place other than that it was abandoned and lay deep inside Kobold territory.

Prep

At this point the players had the option of making their own plan. Main part of the plan was the party Druid going to have a chat with the Kobold Druid who was a member of his circle and responsible for the Kobold kingdom. This meant a roleplaying encounter where the Druid first talked with the Kobold ingame. They learned that they needed papers to travel safely.

After this, the players took some time to gather their stuff, bought some travel gear, and set off.

First encounter

Shortly after entering the Kobold lands, the players encountered the Kobolds; one of their Sorcerors and his bodyguard blocked the path and interrogated them. Remembering what the Druid told them, they asked for travel papers. After some haggling the Kobold sold and prepared their travel paper. He also explained the rules (no digging, no cave exploring, no entering Kobold settlement)

Second encounter

After shooting a deer, setting up camp and having dinner, the players go to rest. The following morning, the remains of the deer have all gone missing. The guards hadn't noticed a thing until it was gone, but scouting in the morning finds various tracks of Kobolds around their campsite.

Third encounter

Travelling further, the players come near a Kobold village. Again they run into bodyguards, who ask them about what they are doing near the village. After a show of papers the guards send them back around the village and they continue on their way.

Fourth encounter

In the woods ahead, the players come across the corpse of an Ogre. It seems to have been killed by small stabbing weapons. Doing some research around the site, the players learn that there's more Ogres that left the scene, but no sign of any struggle or marks of other creatures. A little worried, they push further.

Fifth encounter

From up ahead, the sound of giant feet can be heard. Ahead of the party, two Ogres burst from the path, in obvious panic. In an attempt to regain their composure and hide their fear, they act tough and threatening to the party, which takes no time to answer equally tough and a short fight breaks out. (The Ogres are not much of a challenge)

The players wonder amongst each other what scared these Ogres so much, and remembers the other corpse they found. More worried, they push on.

Sixth encounter

The morning after battling the Ogres, as the players break up camp, they encounter a necklace made from Ogre teeth hanging near their tents. No tracks of any creature can be found, and the night guard hadn't noticed a thing. The players decide to put up an extra watch from now on.

Seventh encounter

After a few days of finding little but the occasional Kobold guard near a village (at this point they've seen enough of them that it becomes mundane, and they are mostly just a quick reference unless they have something important to say) the players start coming closer to their goal. During the day, they notice a hawk that seems to follow them around. In the evening, as they make camp, the hawk sets down nearby to watch them. The party Fighter, being ever the pragmatist, decides to shoot it. The following morning as they wake up, the Ogre-tooth necklace has been stolen, although the Fighter was wearing it as they slept. The night guard, again, saw nothing. The players are now extremely worried, but realise they can only push further.

Eight encounter

The players spot an abandoned castle on a hilltop. Curious about whether this is their destination, they decide to ask the nearest Kobolds about it. The Kobolds tell them the place is haunted and they never go there, but it's not the temple they are looking for.

The word "haunted" seems to draw the party's attention, and they decide to check it out in hopes of finding treasure.

Ninth encounter

The players check out the castle, which indeed turns out haunted. As they walk around, various mysterious things happen (fires suddenly going on, wind blowing inside buildings, rumbling sounds). As the players are eager and continue to explore, I realise they are probably looking for something exciting, so I fill in the haunt by having Elementals appear from the castle, which engage them. The players realise they've bitten off a bit more than they can chew when after the first wave, a second, much larger Elemental starts to form nearby, and quickly leave. (I make a quick note that they might want to come back here later)

Tenth encounter

The players push further out, until they see in the distance two openings in the woods, fairly close together. At their next chance they again ask one of the Kobold guards whether this is their target. The Kobold explains that one of the two is a large Kobold city, which is off limits, and the other is their goal. He also tells them the Kobolds never go near the temple, or the city it's in, but that it's all on them what they do.

Arrival

The players arrive at their destination after a long, dangerous journey through Kobold lands. They are still full of questions about the Kobold empire and the strange things that happened to them, but they set it aside. As they travel inside the city, many more exciting things happen, but their travel is over. It took about 4 hours ingame time if I remember right, and certainly felt like an adventure. And of course, there´ll be a trip back if they make it through the temple. During that return trip, at the very least they´ll run into the mysterious Kobold Giant Hunters they heard all these rumors about...

Summing up

TL;DR:

• most encounters shouldn't revolve around something killing the players, especially not routine travel in civilized lands. Creatures are generally not suicidal and have their own lives. Goblins also need food, they also farm, mine, build, trade, etc.
• the more minor things you let happen on a travel, the longer it feels. 6 very short (5min or so) roleplaying encounters with a "you travel 3 more days and then.." feels much more like an actual travel then "you travel for 3 weeks".
• using minor non-combat encounters can help you show how the landscape and country changes, as you'll have time for it without making it super obvious.
• don't just drop random encounters on players; foreshadow them with said minor encounters. Fighting a monster is much more interesting if you've seen what it's done with the local area first.
• things don't randomly bump into each other. Usually one side goes actively looking for the other; use this to make the story more interesting.