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.
I'm leaning towards corrupt geometry right now. None of them seem to be lamina faces, and I "click-checked" vertices to be sure that two wern't overlapping (un-merged). I've also double-checked all the cleanup settings (and the low res mesh, just in case). Think I may have to export the smoothed mesh to another software to…