speaking from experience in the field of subterranean building (example here of an Underdark project I had a while back -> http://imgur.com/a/IIaEG
) , it's not really an issue to hollow out a cavespace (mind you, depending on if you want a surface realm directly above the underdark can be a trick - mostly the lag and the height limits can be a smidgen of an issue) it's just a matter of knowing what you want and how you want it done
I can most definately say that Voxel is the single most useful tool I've found for large scale environmental alterations, what could take you weeks by hand takes about 10 minutes with voxel brushes; though for the finer details, nothing beats a handmade product, right?. It's probably also worth, if considered doing it - having a worldpainter map, mostly so you can manually alter the levels of things (where the surface starts, if you want a surface at all ect), could even go for a full height map of just stone and hollow the inside space as you see fit for the many layers of the underdark! Then again, you also have a lot of limitation with the very select materials readily useable in minecraft without the use of mods - flora and fauna, materials to build from etc, and until the API comes out (probably never will T_T) you're sort of cut off at the knees about the capability of customization of a multiplayer environment. Single player would be a lot easier, but where's the fun in that!?
*rubs chin thoughtfully
* all these ideas really get my fingers itching to make it all xD