Those of us who played adv mode before the Z-level update remember all the fun ruins and the like that used to exist in the world map.
What I proposes is that history begins with a "pre-history" phase that lasts say five hundred years. At this point, people do not hunt megabeasts, they only worship them. Human, goblin and kobold sites are dominated by huge pagan temple-like structures (like the ruins from adventure mode in early versions of this game) dedicated to a powerful megabeast. Then, at some point in history, all of these megabeasts run amok and destroy their own cultic areas (they are not threatened at this point, because no one fights back), leaving behind ruins with weird artwork that hints at the megabeast that used to live be worshipped there. All history from these civilizations is erased, more or less. These ruined pre-history cultures supply the world with fun places to explore and loot in adventure mode, and perhaps might contain a sleeping or otherwise dormant megabeast guarding a huge pile of loot.
Then the world is re-seeded with more stable, non-beast-worshipping people who build the regular towns, retreats, fortresses, caves, etc. that we recognize now. From this point on, history is recorded, and the older destroyed sites are either forgotten or remembered in vague legend.
The point being, I miss those wacky old undead infested pyramids, and would love to see them return in some form that meshes well with the current world-gen system!