I vote for deformable terrain. Then players could "dig" mines into the ground anywhere! (preferably close to cities...) Vast tunnel networks would form, and there would be rampant cave-ins and water management issues (since the water table is pretty close to the surface in most places where humans live)...
That being said, if deformable terrain is too difficult to program (I'm not volunteering for that project!) then how about a nice (or several) pre-rendered mines with different cave in points. Then the mine would start out totally caved in, and players would have to clear it to get to the depths. Instead of digging for specific things, you'd just "dig" anywhere in the mine, and then you might find something depending on how deep you were in the mine! So if you're near the surface, then you might get some clay, but if you're 1km deep in the tunnels you might find coal and iron. There might even be hot spots (like a coal room?) near the surface...although to balance it, there should be dangers on the way to the hot spots that are comparable to the reward of getting the item...
Digging out the cave-ins would be accomplished with a pick-axe, magic, or some combination of the two! Then the cave-in zone could be reinforced by crafters...or something like that.
I'd like to see a more elaborate mining system - one that is at least as complex and fun as the combat system.