The troll example may work in the late game (it is tough) and if it is near so the player may react on the event. However if it has been triggered in some distant area the ammount of generated trolls would became overhelming.
Well, I don't think its necessary for all dungeons to have linear growth, otherwise they go right back to appearing "canned." In some cases, a population of monsters might decline because they can't find enough food (the player may keep killing all of their raiders before they attain any success) or they could splinter on their own or even succumb to other, different kinds of monsters independant of player influence.
The whole point of the post to begin with was to propose making dungeons seem like a living part of the world, rather than just "goodie spots," so they should succeed and fail in the same way as a standard opponent might. Rather than simply have dungeons emmerge at random, I would like to see populations of monsters, dungeons, etc. be created at the beginning of the game (as though they were already there), and then allow them to grow and change as time goes on. If a dungeon emmerges in a player's territory, it's because there are forces (like other monsters) in the wilderness that are forcing or encouraging monsters to move into the player's frontier. So in other words, nothing simply "spawns" our of the blue. For instance...
Let's go back to our troll tribe. At the beginning, they start in the wilderness a good distance from any player settlements. They grow nicely until they are large enough to catch the attention of a local, hungry drake. Player X watches with a ranger from a healthy distance as the drake gobbles down dozens of trolls, and the rest flee in small groups in every direction. Some go deeper into the wilderness, but some end up at the edge of Player X's territory. Wherever they end up, each group creates a small mini-tribe. Now, multiple things could happen. Player X might decide to take no action at all and there is a small chance that the troll tribes will remain peaceful or simply die of starvation (whether they starve could be based on the favorability of the terrain). Idleness may also allow them to grow and gain confidence, however. If the trolls begins to raid Player X's territory, Player X may simply kill the raiders and cut off their food supply or he may go straight to the source and erradicate the tribe alltogether.
Now, I understand that having hundreds of monster tribe/troupe/group mini-opponents can cause any computer to huff and puff, but their behavior and growth algorithms can be very simple, and they don't need to behave intelligently like a human or AI opponent does. There would be some balance issues to work out (for instances, if there are numerous competing monster types in the wilderness, you need to make sure that one doesn't end up dominating the world and the others go extinct too quickly--- perhaps certain monster types would grow/defend more capably on certain terrains?) but this kind of element would add greatly to making the world appear alive.