Derinkuyu wasn't discovered until 1965, when a resident cleaning the back wall of his cave house broke through a wall and discovered behind it a room that he'd never seen, which led to still another, and another. Eventually, spelunking archeologists found a maze of connecting chambers that descended at least 18 stories and 280 feet beneath the surface, ample enough to hold 30,000 people. [flickr]. [wiki].
Wieliczka Salt Mine in Poland has been in operation for 800-odd years. Needless to say, this has given the miners plenty of time to carve some pretty amazing things. More photos here and here. Videos here and here. Virtual tour here. Wikipedia.
The gypsum crystals in the Cave of Crystals at the Naica mine in Chihuahua, Mexico, are some of the largest and most spectacular in the world. [Last link is a .wmv]