Sorry, I'm late.

This was how it sometimes looked before the fix for the current size settings:

Seeing your former wireframes and seen this, I think the issue you have is called "T-junctions". It can be partially blamed to the limited precision of digital numbers, but even in real life you cannot represent some values simply by reals. e.g. 1.0/3.0 == 0.333333....
(I'll avoid a long/boring explanation, derailing your dev-thread, but let me know if you want to hear it )

On the positive side, that issue was well known for a long time. (e.g. BSP compiler ran into it). The solution is called "half edge" data structure (or "representation"). You simply extend the way you represent meshes a little bit. Instead of having faces (in your case probably always quads) that hold references to vertices, you introduce a step in-between by referencing to 4 edges that reference to the vertices. (quads->faces[4]->vertices[2])
For rendering, you need indices and vertices, of course. But that's very easy to generate from the half edge representation. The BIG advantage is that edges are shared between two adjacent faces (quads). if you "Split" an edge, your both neighbour will realize this and can generate an index/vertex mesh with taking this split-vertex into account.

The way I've implemented it is to have a "flag" in my "edge" struct that specifies whether the two referenced items are vertices or the two sub-edges from a previous division. This way, during "splitting" I don't even care about the neighbours, as these implicitly will know about it when you bake the half-edge-mesh into a triangle mesh.

there is a lot of further reading of about it, a more visual and practical guide: http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

It might look a bit exhaustive at first, but it actually is quite simple to implement, BUT this will eliminate 100% of the issue, worth the effort IMHO