Would it be possible, given an arbitrary point P, and assuming I can look up nearby (unmeshed) points sorted by distance, efficiently determine the three nearby points that form the delaunay triangle which contains P? If so, how?
I assume you are in 2D with no collinear points. What I propose also works in 3D. Build a Kd-tree containing all the points. Then look for the 2 nearest neighbors of P. Construct the circumcircle.
Consider the center of that circle and look for it nearest neighbors. If the first point you find (ignoring the triangle points) is further than the circle radius, then you have your triangle. Otherwise, the empty-circle property is violated and in that case you know that the point is outside the triangle. You can now define two triangles and check that the empty circle property is verified like done before (but in the case you find a point in the circle, I think you need to check whether the point is inside the triangle). Then it's like doing a Delaunay triangulation with all the fours points and all other points you find inside a circumcircle.
For the implementation, you can use CGAL for example which provides Orthogonal_incremental_nearest_neighbor, the has_on_bounded_side function from the Triangle_2 class and the circumcenter function.
You can also use the directly the Delaunay_triangulation_2 class initialized with the three first points and insert incrementally points invalidating the empty-circle property of the triangular faces.