This borders on a bug...
I've been working with terrains that have a portion of nodes in a grid pattern. The points are two-dimensionally equidistant and ArcGIS (10.2) seems to use a randomization method for deciding which diagonal to triangulate across given a perfect square of points (2 dimensionally). Each time I build the terrain with the same points, different diagonals are chosen. I even have some evidence that triangulation was somehow re-randomized within a terrain that was not rebuilt (I just moved the geodatabase between drives).
This results in an unpredictable surface model.
But the points are not truly equidistant when considered in 3 dimensions (including z-values). Shouldn't terrain triangulation consider z-values to find the shortest diagonal?