The mine shafts are what happened when people's houses on SMP servers were buried by the earthquake of not needed map resets.
It's doesn't go with the topic much, but I have had a theory about the strongholds. The Endermen made them. Think about it. 3 block ceilings, End portals, jails for trapping people. They also hired the silverfish to guard the End and their hold.