I run into this issue all the time and it's really frustrating to fix especially on high poly meshes. Either there's no face joining some edges ("zero-area hole"?) or there is a zero-area face. Either way it messes with the normals making ugly black spots all over the mesh. Here's an example:
To fix the normals I'd quite like to either...
split the upper face, as the dashed line shows,
or merge the two lower faces by dissolving the edge, as the cross shows.
How can I do this automatically to the entire mesh?
Manual methods aren't acceptable as there's a lot of this kind of geometry. I'd prefer to change the mesh as little as possible, or at least not lose any information by collapsing huge areas.
Sometimes is's hard to actually select the face and I resort to selecting an adjacent one, growing the selection with
Ctrl Numpad+ and deselecting the others. Once selected, others can be selected with
Select->Select Similar->Area. Adjusting the threshold is often necessary to avoid numerical inaccuracies. It also helps if the model is not too small, so maybe scale it up first.
Below is an example of a zero-area hole, although I've moved the vertex up so you can see it.
You can get the zero-area faces back with
Mesh->Clean up->Fill Holes.
Even if I do manage to manage to get rid of the zero-area face, leaving a quad as shown below, I've found triangulating it splits the wrong way and just gives a zero-area face again (this really seems like a bug in blender's triangulation).