I know its not too much help, but i know that with unreal tournament 2k3/2k4 caves are made by simply transforming the terrain to be (for example) one on top of each other, of course this is very limiting, but it allows you to employ the normal LOD algorithms involved with terrain rendering.

hope that helps
-Dan

hmm I think a terrain based on voxels could do that. Try googling "voxel".
And I think I remember of a guy here in gamedev who posted screenshots of a terrain made with this method (he had some problems texturing it) so you can also try to search the forums here (I think with "voxel terrain" you'll have some good posts)

Voxels are great but they're still a bit far off from being a practical option in todays games.

With that said, there is relatively little work on terrain rendering with overhangs and caves and voxels do tend to be the standard approach.

I would suggest using ChunkedLOD. The input geometry is generally a heightmap, but that is not necessarily a restriction of the algorithm. You can use the progressive mesh algorithm to generate your LOD levels from arbitrary geometry and simply use those chunks at runtime.

You'll have to use a different method to patch up cracks, since skirts obviously won't work too well.

Texturing also might be a bit more complex, but I would have to think about this more to come up with a creative solution. I am confident that a solution exists, it just hasn't been invented yet, as far as I know.

Also, it would be quit difficult to make your terrain dynamically destructible using this method. Progressive meshes are relatively fast and could potentially be used to rebuild your LOD levels at runtime. You definitely wouldn't want to recalculate more than a few chunks per frame so it's simply going to depend on how often things get deformed. Note that several deformations could occur on the same chunk and that would be fine, since it's still one chunk that you have to rebuild.

Anyway, I need to get back to work. I hope this helps. Good luck with everything.