>   However, it seems to me that the NODES version requires the linear
>   search at the end of PointLocatorTree::operator() to be involved more
>   often than the ELEMENTS version; in particular, the ELEMENTS version
>   did *never* need the linear search in the case for linear elements,
>   whereas the NODES version does (in my case, for linear TET10
>   elements).  While I don't doubt that it is still much faster in the
>   mean, it causes approximately two problems for my application:

>  1.) Since I am using out_of_mesh_mode, I get wrong results, since the
>  linear search is disabled in out_of_mesh_mode.

Dear Tim,
this sounds strange... the NODES BOUNDING BOX version should avoid (completely in case of elements with rectilinear edges) the linear search for points within the mesh.
You shouldn't  find any element forcing the linear search in out of mesh mode.
With the ELEMENT CENTROID insertion method (revision 1.19) the linear search deals with the particular situations in witch the point you are searching isn't contained in any element assigned to the node of the tree that bounds the point.

Using the NODES BOUNDING BOX version you could check if you need the linear search to find points seeded within the mesh. If this is true there could be a problem with the algorithm.