3 points are needed to define a plane. Newell's method is known to fail if the 3 points are chosen around a concave corner - the normal of the resulting plane will point in the direction opposite to the expected one.
Are there any improvements to Newell's method that help in choosing a valid starting point? Or is there an alternative algorithm that doesn't have this issue?
Since your only interest in the plane is whether a given point is "deeper" or "closer" than it, I suppose you expect the normal of the plane to point towards the viewpoint (or away from it, depending on your convention). So just calculate the dot-product of the normal and the vector from the viewpoint to one of the three points, and look at its sign; if it's positive when you generally expect negative (or vice-versa), then reverse the normal.