Resampling works perfectly now. It turned out I was doing some rather bone-headed things, like doing a linear interpolation between a point and itself. Also, I the number of points inserted between two critical points is now a function of the portion of the total stroke length that is contained between the two of them.
I've also tweaked the graph-based hair removal algorithm. Consider the lower left corner of the image shown. Once the two hairs of the Y-like shape sticking out are removed, what we have left is another hair. Previously, the hair edges removal was all done in one pass, but to remove newly formed hairs we now have to do multiple passes (as well as keep track of edges per vertex, so that we know when what was formerly an inner vertex is now an endpoint). In this particular case, the unremoved hair wasn't actually having a detrimental effect, since the shape could still be represented by a single stroke.