This geometric situation is often called a t-junction, since the intersection of one edge with another resembles a T. This problem is illustrated graphically in the RedBook (a diamond with a T in the middle).
Whether you should calculate normals at these t-junctions depends largely on what you’re rendering and to what degree your object relies on vertex adjacency. For instance, if your’re using per-vertex lighting, and you have a coarse subdivision in your model, then interpolation artifacts could be severe. To make matters worse, cracks can appear in the rasterization between these problem edges. You might therefore consider fixing the t-juctions, which is related to your second question.
Finding the distance of a point to a line is easily determined with a little vector arithmetic.
/ | D
A o--->--o-------------------------o B
Here, A and B are two end-points of an edge; V is some vertex on another edge we’re testing for a t-junction; D is the distance from V to the line segment AB; and E is the normalized edge direction (B - A) / length(B - A).
If V is on the edge AB, then D = 0, so we need only solve for D:
D = length(V - (A + E * dot(V - A, E)) ).
Due to floating-point math, this calculation will seldom yield a 0, so you might consider anything within a small epsilon to be on the edge. For example, if D is lest than 0.1, then insert the vertex V between A and B. If V is between A and B, then dot(V - A, E) is greater than -e, and dot(V - A, E) is less than length(B - A) + e, where e is some small value to account for floating-point error. It’s also important to snap vertices consistently so as to avoid creating gaps where you intend to remove them.
Note that if you’re using per-pixel lighting, then normals may not be a problem, but the cracks could continue to be a specter. It all really depends on your particulars.
I hope this helps.