3. 13th Age has the concept of Living Dungeons, highly magical entities, which bubble up from deep in the earth before breaking out on the surface. This is somewhat similar to, and probably influenced by, Philotomy Jurament's notion of the Mythic Underworld - a megadungeon with an evil intelligence and some level of supernatural control over its contents. I think, though I'm not sure, that the Mythic Underworld may be able to create more rooms and 'grow' inhabitants.
4. A recently crashed spaceship or skyrealm, or a vast beached sea monster.
5. New magic has been developed such as the ability to breathe underwater, fly or travel into space or to other planes, which opens up more adventure locations.
6. A new dungeon has simply been recently built, such as a fort or the lair of giant social insects.
7. A dungeon that somehow resets itself, after it has been 'cracked'. Perhaps there are hidden mechanisms, or an army of automatons. They could even mine more treasure.
Good point. I mentioned this in the context of old dungeons being uncovered by recent events (such as a landslide or erosion), but I didn't really delve into the idea nearly this deeply.
Yes, new 'dungeons' are springing up all the time. More to the point, new dungeons become old dungeons over time. So after those giant insects build their lair, and then some humans come along and exterminate them, a group of kobolds might move into the tunnels and take them over for their own purposes. Then an owlbear might come along and dig up some of the tunnels searching for kobold snacks, and the surviving kobolds might ward it off with stink bombs and brick over the tunnels leading to the owlbear lair. Later, a young dragon might drive off the owlbear, and kobolds might build a temple to the dragon and offer it sacrifices and treasure, so that the dragon tolerates its neighbors. The kobolds continue mining until the break into a natural cave located below the complex, at which point the troglodytes lairing their start warring with each other, and so forth.
Some other examples of the same idea:
8. A household experiences some evil tragedy and their dwelling becomes newly haunted.
9. A settlement is destroyed or abandoned after some disaster, and the ruins are colonized as a convenient lair by some monster.
10. A lich or similarly powerful figure commissions the construction of a new tomb, either as a lair or as a resting place for some treasure which the builder wants to take out of circulation.
11. A mine, quarry, catacomb, sewer, viaduct or other underground construction has to be abandoned after a monster decides to use it as a lair, or after the builders accidently break into an existing dungeon of a different sort releasing horrors into their workplace. Or, perhaps a city has extensive quarries underneath it built to support construction in the city, and at some point the city decides to repurpose the empty quarries as catacombs, but in result the catacombs are now haunted by the restless dead who are disturbed by the overly hasty disinterment and interment to new accommodations.