Notch wrote his Minecraft system in a very simple way. Only faces with no neighbors will actually render faces, and faces are sorted into six different lists. These lists sort faces into up, down, north, south, east, and west, and only the faces facing toward the player’s view angles will actually render. This is a really clever way of dropping the polycount.
Essentially, he is storing tile types in an array, and generating meshes based on those faces that are exposed.
Notch previously worked on a project called Wurm Online, and developed a mining engine (the game had a modifiable heightmap, like you described), and the way that they managed holes in the terrain, was simply, to not render triangles over mine entrances. When the player collided with these triangles, he would fall through them, and change scenes to the underground scene, which used square blocks to represent mined out segments. This was a one-dimensional array which stored if a tile was mined out, and the floor/ceiling height of that underground tile.
Search this forum for “holes in heightmap” to find several rather clever methods of managing this.
I would also suggest some research into a marching cubes algorithm.
I’m working on a side-scroller right now that features terrain modification, and luckily, since orthographic displays make this very simple, I can essentially just pop a tunnel in front of the terrain instead of digging into it. Let’s face it though, this is much more difficult in a 3d implementation, and I doubt many people are going to be willing to help you on this subject…
I’ll try to help you further if you run into problems with an actual implementation, but I can’t promise anything.