| Very happy to see this thread bumped. I wanted to bump it for a long time but I was the last poster so I didn't want to be too overt about it. In regards to random encounters I'd like to get a little more mathy without biting off too much work for me :-P
First, it's easy to justify increasing the level of random monsters as the party levels up. Clearly they're killing off/clearing out part of the dungeon and potentially raising alarms. Of course, the choice is yours should you decide you would rather let floor = encounter level. I'm going to use mostly small dice for this as an example of how one might make a decent set of random encounter tables. These borrow from a concept I read in mike mearls' blog about using wide rather than tall tables.
Ok so to start, pick a level, either based on the party or based on the floor. Take the result from that roll, and roll from each table it proscribes. This second layer of tables is based on similar xp values:
Level tables
Level 1: 1d6
1: roll twice from 200XP (easy)
2: roll twice from 200XP, once from 100XP (normal)
3: roll once from 300XP, once from 200XP (normal)
4: roll twice from 250XP (normal)
5: roll once from 200XP, twice from 100XP, once from 125 XP (normal+25)
6: roll once from 300XP, once from 200XP, once from 125 XP (hard)
Level 2: 1d6
1: 250XP twice (e)
2: 375XP and 250XP (n)
3: 375XP and 125XP twice (n)
4: 300XP and 200XP and 125XP (n)
5: 250XP twice and 100XP twice (h-50)
6: 375XP twice (h)
XP tables
100XP: 1d4
1: 1 Goblin Skirmisher
2: 1 Kobold Slinger
3: 1 Goblin Blackblade
4: 4 Goblin Cutter
125XP: 1d4
1: 1 Goblin Sharpshooter
2: 1 Guard Drake
3: 1 Kobold Dragonshield
4: 4 Human Rabble
200XP: 1d4
1: 2 Stormclaw Scorpion
2: 2 Goblin Warrior
3: 2 Kobold Skirmisher
4: 8 Decrepit Skeleton
250XP: 1d4
1: 2 Zombie
2: 2 Gray Wolf
3: 1 Elf Archer + 4 Human Rabble
4: 8 Kruthik Hatchling
300XP: 1d4
1: 2 Zombie + 2 decrepit skeleton
2: 2 Goblin Skullcleaver
3: 1 Kobold Wyrmpriest + 2 Kobold Minion + 1 Kobold Skirmisher
4: 1 Ochre Jelly
375XP: 1d4
1: 3 Elf Scout
2: 1 Hobgoblin Warcaster + 1 Hobgoblin Mercenary + 1 Goblin Blackblade
3: 1 Human Gaurd + 1 Human Bandit + 1 Fire Beetle
4: 2 Hobgoblin Grunt + 2 Hobgoblin Archer
End of Tables
Obviously I went with very small die sizes to keep from going overboard, and limited myself to two levels. Also I picked XP values as the titles for tables to make my intentions clear, but it may be easier to give them generic titles like "1-1" or "1-3" for "Level-NumberOfMonsters". Naturally you could add another layer by actually dividing out the different races rather than letting them end up mixed up all willy-nilly (might be a bit odd to have elves and kobolds working together) to increase the options, or just use a bigger die than d4. Near the end I started getting creative with XP totals with some tricks such as 3+2+1 gives you the same total as 3 2s, or combining a pair of 3s with a pair of 3 minions (off by only 1xp).
There is a lot of flexibility here, allowing you, the DM, to come up with some interesting (and decidedly random) wandering monster encounters. If you were particularly attached to the "sandbox" mentality, you might even make a large enough table of monsters, then strike out each entry of monsters as the players defeat them, essentially creating a more mobile form of "clearing out the dungeon". You might even concoct scenarios such as "monsters escape and warn others" or "the great relic has been stolen and the alarm is sounded" to justify rolling additional times or re-introducing previously defeated monsters.
A final note: the tables as written are intended to allow you to generate a complete, level appropriate, encounter for 5 PCs. Obviously you can mix and match for more or fewer PCs, but if you are subscribing to the "wandering monsters dogpile" method of making wandering monsters more dangerous, just decide how much XP you'll add to an existing encounter and then roll. Example, if the PCs encounter a level 1 encounter and you want to make it more difficult by a single level, roll from the 125xp table (the difference between 500xp and 625 xp). Or, if you only have 4 PCs, roll from the 100XP table (to go from 400XP to 500XP).
Hope this gets some more gears turning! | 
And yet another word from our sponsors
