Yeah, trying to make natural-looking scenery and stuff is about as hard as it gets. There are a few popular methods but they're all usually the same thing in essence: make a grid of blocks, then manipulate them as simply as possible. The thing is, VM only works to a certain point with ONE solid. But you can do anything if you create lots of little solids that you VM separately.
I suggest you simply break up the place you want to put the cave into several cubes (use carve to slice a big block up into a grid - make your carve selection, then click the button again and again until its all white - that way you cut the thing up but don't lose any bits).
Then delete the cube that you want to be the actual hole, and manipulate the blocks around the gap. Here's a drawing:
----------------------------------
| -------- |
| |_|__|_| |
| | |**| | |
| |?|??|?| |
| -------- |
----------------------------------
Delete the cube with the asterisks in it, and then grab the corners of the cubes around that one, and pull them around to round off the hole. It'll look more natural if you use different sizes of cube.
Rocks... again, use more than one block, and manipulate them as simply as possible.
A tut... yeah, it would make a good one
Sometime...