Efficiently generating mesh for self-generated voxel grid
So I've been all around the houses on this looking for an answer. In the end I found a combination of techniques worked quite well:

To take advantage of all of the 'empty space', the concept of 'surface tracking' from the Octree Decimation paper useful - you can follow the surface from cell to cell and ignore all of the cells in the middle.

The main advantage of generating the voxels ourselves is what we know two vital pieces of information: firstly, the exact position of each vertex within the cells on the 'front' surface; secondly, the 'orientation' of the mesh in each region and which way that 'front' is to be found.


Putting all the pieces together I came up with this Dual Marching Cuboids algorithm, that has pretty good results in very reasonable time.