First: Taking the suggestion in Underworld & Wilderness Adventures more literally. Page 6 tells us to place the special treasures (and special areas) first, then randomly assign monsters, treasures and traps, leaving most of the rooms empty. What I'm thinking: the map should actually reflect this fact. Start with a concept for your megadungeon, then create related concepts for each level; for each of these levels, brainstorm a list of related areas. For example, if you have an "undead city" level, come up with a list of special rooms or areas that would fit into the theme "undead city":
- graveyard (dig here for treasure, risk resurrecting more undead)
- undead temple (undead "priest" turns Lawful clerics)
- throne of the lich-king (might or might not be a full-powered lich)
Second: Cut the connection between individual rooms and individual encounters. Decide what the monster theme is for each region: maybe the graveyard on the undead city level has skeletons, zombies, carrion crawlers, flesh-eating centipedes, and rats as its primary monsters. Also decide what the typical room-type(s) would be in this region: the graveyard can be surrounded by crypts, repositories for cremation urns, funeral niches, and pits for bone fragments. Use the One-Page Dungeon format for each region, and list these room types and monsters off to the side of the map. Number the encounters as usual, but treat this as an "encounter roster", perhaps sorted by room type. The map itself is only labeled with room-type codes.
When prepping the level, randomly stock each encounter as if it were a room, but don't place the number on the map. Leave "empty" rooms blank. During play, describe each room based on its room type, randomly select an encounter from the roster; after all, these monsters, unlike any special encounters, are moving into rooms that are already there and converting them into lairs. Ad the encounter numbers to the map as you use them. Cross off used encounters from the roster as they are cleared; fill in some of the blank encounters between sessions, to represent new monsters moving into cleared rooms. When all encounters are crossed off, redo the monster list using only vermin types; this area will now be mostly monster-free.
Third: Leave lots of blank space on each level. Make a level-wide sketch-map that just shows squares labeled with each region name and lines indicating major tunnels that connect the region. There may be numerous rooms between each region connected to the tunnels, but these can be left unmapped until needed (pull out a geomorph as needed, or fill in an area between sessions.) You can note monsters for minor areas directly on this map, using letter codes.
Fourth: Periodically update the sketch-map to add new full regions. Instead of marking areas "under construction" and asking players not to explore there yet, leave long stretches of simple tunnel and have monsters in a new region dig a passage into the existing complex as each region becomes ready. Also periodically replace completely cleared regions that the PCs rarely visit with new special monsters; maybe if the players have sanctified the cursed graveyard and slain all the undead and carrion crawlers, after a couple months an expedition of trolls moves in and converts the cemetery into a shroom garden; occasional trolls and shriekers wandering into nearby regions may clue the players in that something has changed.
I may have some more to say on this later.