I export meshes frequently from Terragen and always found the best results, as Cyphr mentions, with a top down projection. Camera projections are always incomplete and as you say, full of holes and other issues.
The output meshes are particularly dirty, but you have to remember they are produced by the micropolygon renderer and as good as the output from the render, the higher the detail setting in the render the better the resolution of the mesh, but comes at a cost of file size which can become unwieldy.
A tip for reducing the micropoly file size is to turn off the texture option (UV's) in the Micro Exporter - the UV's are not much use any way (you would have to re-project them) and can reduce the file size significantly.
With this workflow I then find that to properly clean the mesh, duplicate vertices need to be removed, in fact, these meshes always have each vertex duplicated. Since Maya is exceedingly crap at dealing with mesh operations on meshes that can be very dense like terrains, I usually run the mesh through the Duplicate Vertex filer in a program called Meshlab (very quick!) and the mesh is clean. (
http://www.meshlab.net/)
Another way to create a mesh and have a much cleaner output is to export a vector displacement map - see my tutorial -
http://www.planetside.co.uk/forums/index.php/topic,21311.0.htmlYou could then import this map to displace a plane in Mudbox and have a very detailed quad mesh of your Terrain ( I see you mention Zbrush, I would imagine the proceedure is much the same) and with vector displacements overhangs and holes can be preserved.