I don’t know of any games, but I think that a simple cellular automata based generator would produce cave-like veins. For example, in the picture below, the white could be empty or soft stone and the black could be hard stone or undiggable stone.
I think that a perlin noise generator would work, too, as they often are used for natural-looking patterns.
In either case, this phase would just generate the veins in the rock. The rest of the features of the mountain (lava, water, lairs with existing tribes, etc) would just be dug out from whatever this cave-vein-generation phase creates using the existing algorithms you have.
Reason behind this is that I don’t think it’s interesting to dig a dungeon from a blank canvas every single game, it’s too easy. There was a good post on the Steam forums a few months back by some other guy that echoed a similar sentiment.
As for seeing stuff in advance, the system that exists now, seeing two or three squares into the blackness, seems to work well enough.
