If you provide approximately one control point for every few triangles in the mesh and the curve is not self-intersecting and path search still fails them you have to fix errors in the mesh. A small hole or non-manifold edge can throw the algorithm off.
For more robust geodesic path search, which also provides superior results, because it can cut across surface cells (not just connecting mesh points) you could try this method:
It has C++ implementation with MIT license, so you could turn it into a VTK filter without redeveloping anything.