For example, the random encounter table for the Cave of Burning included every demon below a certain CR, every creature with the [fire] subtype below a certain CR, several fire-related non-creature encounters, and creatures which wandered in from the surface or from connected caves.
Each time a party enters a new room, I rolled to see if there were creatures there. I never got this system perfected. I was mostly using d2s, and then not rolling for a cleared room for a couple days after it was cleared, before going back to rolling for it again. If I were to go back to a system like this, I would probably roll 1d4 (1 = no creatures; 2-4 = creatures) for an unexplored room, 1d2 for a room that was previously cleared or empty.
Then, after I perfected a dynamic random encounter table for the gladiatorial arena, I realized that, as much sense as it makes for the arena, it makes even more sense for encounters out in the wild.
The principle is this: you have a list of all the encounters that one might find in a given area, and each one is associated with a number. That number is how many encounters of that type are wandering around in the general area, and it's also a range of numbers on the die. Each time the party eliminates an encounter, tick this number down by about one.
The approximation is a judgement call. If the encounter was "1d6 bugbears", and you rolled high so the party encountered and killed 6, consider ticking the number down by two. If you rolled low and they only encountered 1 bugbear, consider not ticking the number down at all.
If half of the encounter escaped and the other half died, consider ticking the original down by 1, and add an extra encounter to the list consisting of exactly the number of creatures that got away (with a note to yourself specifying which PCs they now know to fear).
If the party encounters an immobile encounter and does not kill it, tick it down from the random list and add it to the map as a regular (i.e., non-wandering) encounter. Shrieker fungi don't tend to wander away. (Obviously, if the party does kill something, you should add its corpse to the map.) If you get an immobile encounter in a previously-cleared area, feel free to reroll unless you can quickly think of a good reason how it got there (or if you feel like saying "sure let's go with that" once one of your players comes up with a plausible theory).
Also on the encounter list are options to pull from nearby regions. If the Stank Cave is connected to the Don't Drink This River, then the DDTR random encounter table has a "roll on Stank Cave table" option, and the Stank Cave random encounter table has a "roll on DDTR table" option. If this option comes up and the encounter is defeated, you may want to tick the number on both lists down by 1.
For example, if the party is exploring the DDTR and get "roll on Stank Cave table" and then get a shambling mound from the Stank Cave, and they kill the Shambling Mound, that represents a shambling mound wandering from its Stank Cave home to the DDTR. If the shambling mound is killed, that's one fewer shambling mound in the Stank Cave, so you tick that number down by 1. It is also the case that a monster wandered from the Stank Cave to the DDTR and never came back, which may dissuade other monsters from doing the same, so tick the "roll on Stank Cave table" option down by 1. This latter half is probably more advisable if the areas are populated largely by relatively intelligent creatures. If it's all mindless vermin, don't tick down "roll on another table", only tick down the encounter that was actually killed.
Another possibility to consider: you could actually tick the "roll on other table" option up each time you roll it, to signify that creatures from this other location are obviously making efforts to expand their territory, if you're encountering them elsewhere. Or, probably better (if your lists aren't sufficiently segregated by race), you could (on a case-by-case basis) simply move creatures from one list to another. If the party encounters kobolds in hobgoblin-controlled territory, maybe there are a few groups of kobolds scouting out hobgoblin lands on a long-term basis.
The third kind of thing on the encounter list is "Nothing" (which I always set to a higher number than any one encounter, and usually a substantial fraction of the total). Instead of rolling in each room to see if there's a monster there or not, simply always roll on the random encounter list, and if it comes up "Nothing", there isn't a monster there.
Never tick "Nothing" down. As adventurers exterminate monsters, the likelihood that they encounter a new monster grows ever smaller. This is perhaps the most elegantly simulationist aspect of the dynamic random encounter table, and the part that most closely cleaves to the philosophy of the Open Gaming Table.
More monsters can be added, though I would suggest each time new monsters come in it be treated as a medium-big deal, and possibly be a quest hook. The surface random encounter table (yes, you should have one for the surface, though its "Nothing" value should be higher than in the dungeons) looking a little sparse? Add a bunch of bandit encounters to the dynamic table and have some villagers mention a recent surge in bandit activity, and build it into an adventure where you hunt down and kill the bandit king, which doesn't eliminate existing bandits from the table, but it means more bandits won't get added.
I originally had all my random encounter tables set to total up to 100 (so I could roll a d%), but that doesn't work if you want them to be dynamic. Then I realized: heyy, I'm using Excel (Excel is easily the most useful program I own, don't knock it), I've got the RANDBETWEEN function, I don't need to aim for a target number at all. So now I have some dynamic tables in the 80s and some in the high 200s.
For those of you playing along at home and want to know exactly what format I'm using, each table has six columns, of which the first two are hidden because they're purely for system use. (I could just as easily have had four, and incorporated the first two columns right into the third, but I didn't happen to do that, because it didn't occur to me until after I was done converting all my tables to this new system in the first place.)
Yes, I know this part is of the sort where if you know anything about Excel you'll be rolling your eyes at what a monumental noob I am, and if you don't know Excel you may be baffled and terrified and have no idea what's going on. Indulge me.
The five columns (we will consider row 3, which is the first data row on most of my tables):
A: Min die roll. Take the max die roll of the previous row, and add one. (B2 happens to be empty, but A3 should = 1 anyway, so it works out fine.)
B: Max die roll. Add the min die roll to the number of monsters of this type and subtract 1 (to get a proper dice range - if you have a 5% chance, that's 1-5 on the die, but adding 1 and 5 would get you 6).
C: Dice range. The first IF is to leave this field blank if there aren't any encounters of this type (yes, I know, it would be easier to just check to see whether there's anything in D), mostly so I could leave several blank ones at the end for later use. The second IF is to return a single-number range if there's only one encounter of this type (if there's only one ettin wandering around, it's more elegant if the ettin's dice range reads "82" rather than "82-82"). The third (it was originally a third IF, but that was silly, A3<B3 is the only possibility left) returns the range from min die roll to max die roll.
D: Number of encounters. This is the all-important number associated with each encounter, which you set to however many encounters of this type there are in the region, and tick down every time the party kills an encounter.
E: Encounter name and brief details (e.g., "1d6 Medium Centipedes", "CE Justice Archon wearing a Helm of Opposite Alignment").
F: The sourcebook in which that encounter is found.
And then, as mentioned, you can put an automatic die roller someplace on the sheet. To roll a die and get a random encounter from the table, you can simply do something very simple like this, where # is the last row of the table (it works even if D# is blank, i.e., if you have some blank ones at the end, which you should):
It isn't remotely tricky to hook it up such that it automatically pulls the encounter name/details/sourcebook from the list for you, but I leave that as an exercise for the reader.
UPDATE: I did wind up doing that last bit on my own tables. It involves the vlookup command.
And, as an example of what it should look like (or what it looks like for me): the table for the Dwarven Tombs west of Serpent Pass in my setting: