Random Encounters in D&D4 - not quite 1d3 orcs

One difference I've noticed while reading older adventure modules is the ever-present random encounter table. If you dawdled around in a room searching every nook and cranny for treasure instead of just looking in the logical places and then moving, you would likely meet wandering monsters - the DM would roll a d6 every "turn" (10 minutes) and you'd roll on the monster table on a roll of 1 (with a chance of "you hear weird noises"). And Gary Gygax's definition of a "logical place" to hide treasure didn't necessarily coincide with anyone else's. Nasty.

But as editions passed, combat took longer. If you are to trust the grognards, dispatching 1d4 goblins in OD&D was a matter of ten minutes and subtracting some HP. In the 4:th edition, even kobolds would take half an hour to put down unless you use kobold minions. Or unless you are 5:th level, but then the kobolds are just as meaningless as the minions.

Ergo, if random encounters are to work well without wasting everyone's time with non-plot forwarding combats, a new approach to random encounters is needed. Which brings me to my second point: The weird siloing of monsters that existed in old modules.

See, killing wandering monsters explicitly doesn't deplete monsters from encounters. You have your random monster table with 1d3 goblins, or a gray ooze, or whatnot, and then you have the planned encounters with battlemats, monster strategies, intrigue and whatnot. Now go look at the maps for White Plume Mountain at the top of this page and wonder where in the straight corridors all those monsters lived until they were rolled up on the random monster table. (Grab the 3.5 conversion and the art (maps) while you're at it!)

A different approach that may work better for 4E would be to grab random encounters from the pool of nonrandom encounters. Let me exemplify with a basic routine:
1) Roll a d6 every ten minutes the PC:s spend in the dungeon. (This means a short rest takes you halfway to a new roll for random encounters.)
2) On a roll of 1, roll on table G3 - planned encounters eligible for meeting the PC:s randomly. If the PC:s were taking an extended rest in dangerous territory, you might as well roll on the table too.
3) Table G3 (or whatever) lists the encounters that could realistically be "wandering" about the dungeon. The Goblin King and his closest bodyguards don't appear on this table, but the team of goblins that were supposed to make up the "Kitchen" encounter are. And once you've beaten the Fearsome Kitchen Goblins, there's obviously noone in the kitchen once the PC:s get there.
3b) If you roll an encounter that's already "spent", no encounter happens.

(Mike Mearls has alternative approach - a flat 10% chance of random encounters during short rests. Not a bad idea either, and follows the KISS principle, but it retains the problem of non-plot-relevant encounters.)