The "Voxels" you're talking about aren't real voxels. Voxel is short for Volume Pixel or Volume Element, depending upon with whom you speak. (Is that correct grammar???)
They represent a 3d box shaped volume in the purest form (as far as I've read.) The voxel engines you're talking about worked with heightmaps. They cast rays from the camera/viewpoint across the heightmap, similar to scanline converting a texture across a polygon, but it would display color and height. It keeps track of the highest screen value for the current ray being cast and only draws and gets a texture value when the height being calculated is greater than the highest height.
The worst case scenario is a completely flat terrain. For that though you could just increase the step size (you usually have the ray checking heights at specific intervals.)
In most applications of "voxel" rendering of terrains I remember them also interpolating the texture coordinates, so that one voxel's height could have multiple texture pixels. Most landscapes had about 2x2, 4x4, or 8x8 texels to a voxel.T
