Fixed the book-keeping problem I was having before. Now I do not bother to keep track of incomplete edges, I just look at which triangles are incomplete. This means that I have to loop over more triangles, but if a triangle is complete I just skip it and don't worry about it. I tested on a few random 1000 vertex cases, and a kd-tree one with 10000 vertices, and the mesher does not see to be slower and is now working consistently again.