The Death of Randomness
If there's anything that can be said for sure about 4e, it's that random events are constrained to the combat board, and even then, the range of random events is highly reduced. A creature has an expected lifespan, an expected damage output, and an expected treasure parcel. Encounters are built to minimize the likelihood of a disaster or overwhelming victory, characters are built to withstand the vagaries of the dice, and character creation is more like engineering than hoping for a high STR roll. The general consensus with the New School D&D crowd is that this is a Good Thing.
For a certain play style of DnD, this is a good thing. Knowing what's in the box lets DM's build encounters and whole campaigns with a reasonable certainty and a minimum of chaos.
But for other styles of DnD, randomness is absolutely essential. Not just in combat, but in the whole of the world. Randomness frees the Dungeon Master to be an impartial referee. Take wandering monsters, for example. If you decide that in a dungeon there's a 20% chance of encountering a monster every 10 minutes (or hour, or day), you have set a danger level without coming off as a bad guy. Of course, it requires skill to set these danger levels at something the players feel is logical. Walking through a town shouldn't have an 80% chance of being attacked, and walking through sparsely populated woods shouldn't have the checks made every five minutes. When the DM uses random methods to propel the 'story', it frees the DM to describe the situation and watch what happens, and it frees the players from having to second-guess the DM's intentions.
The Function of Randomness in RPGs
Random events undermine metagaming. Metagaming requires treating the game world as a statistical analysis, or treating the DM's adventure as a predictable narrative. Humans can only make statistical predictions within very tight constraints, however. With multiple variables, predictions outside of the system become impossible. Instead of wondering why the DM isn't letting my amazing tracker shine, I know that within this town there's a chance that I simply won't encounter any badguys worth tracking. It stops becoming about an antagonism between the DM and the players and now the players have to deal with a new situation.
Unpredictability spurs creativity. If the DM doesn't know what is going to happen from moment to moment, plot creation involves finding links between events, strengthening some, pruning others and letting the players move through the world freely. It frees the DM to keep low investment in any one outcome, because a trick of the dice might undo all her hard work.
To some extent, your issue feels more like a bone to pick with lazy DMs who just want to run an "out of box" campaign. The problem you lay at 4e's feet isn't a problem if a DM takes the time to create their own adventure or at least puts a twist on an existing one.
And when you speak of randomness, I think of the real world, but the real world is ANYTHING by random. It's very, very predictable, that's why even in the most "unpredictable" environments such as the battlefield, people are still able to make educated guesses about what they're reasonably going to run into.
Wandering monsters is always something that has bothered me. Monsters don't "wander" for starters, they live in specific environments and only leave them for absolute necessities(or in the case of more intelligent creatures, boredom or mayhem). When wandering through the forest, the chance that you're going to run into anything more spectacular than a pack of wolves is fairly low. Giants, dragons, oozes, ect... these things live in specific places and are usually fairly keen on staying there.
It's far more likely for YOU to wander into their territory(which is often well marked by primitive signs or natural indications), and in such a case your more nature-savvy character should be able to give you a fair warning of where you should or shouldn't wander in the woods. Even the most unmapped forests are likely to have rumors and stories about them, which a party passing near said location is likely to pick up. It is even more unlikely to be walking down a well-used path and run into anything particularly monstrous, you're more likely to get robbed than attacked by a Hag or something.
Metagaming is such a silly term because it so much of it actually isn't, players are going to be genre savvy, if they're not, they're noobs(and that's fine), but they'll learn quickly. Anyone who's genre savvy or played the campaign for more than a few nights will quickly get a hang of how the DM likes to swing things and start checking for that.
In short: reality, which your randomness is trying to imitate, is anything but random(which is why we resort to fantasy in the first place!) Sure, you could have the players mapping an unknown forest in an isolated location with no surrounding civilization, but even then aside from breaking all the rules through hand-waving and saying "well it's magic, so there!" even a cursory glance at the forest will give them some expectation of what to find there. Are there fae? Is it swampy and dank? Is it tall and overgrown? It is cold and snowy? This will quickly give any savvy player a good idea of what they might run into, and a vague idea of even the wildest threats they might encounter.
Honestly, I don't favor a "random" world, I favor a predictable one. It's much more fun to watch the party prepare for the possibility of fighting the green dragon that supposedly lives in the forest and yet never come across it, but instead just get dicked around by the dragon's magic. I would rather my players prepare for a wide range of events that COULD happen, rather than be caught off guard by the Frost Wurm that's wandering through the desert because I rolled 99 on my table of random events.
Random is often no more fun than totally railroaded. Things should be fairly predictable in what DOES happen, but less so in what COULD happen.