Try running this while the object is selected (and NOT in a component mode), it'll break all faces and re-merge them: string $curSelObj[] = `ls -sl`; PolySelectConvert 3; //verts polySplitVertex; polyMergeVertex -d 0.0001; select -cl; selectMode -o; select -r $curSelObj;
Have you tried selecting all vertices (before triangulating) and using weld/merge vertices or whatever its called in maya, lowering the threshold to make sure its not effecting anything you can see, and then checking for ngons? There might be some weird vertices that are messing it up.