Note that just today John submitted some enhancements for PointLocator to make it operate only on local elements: https://github.com/libMesh/libmesh/pull/264
So PointLocator is definitely ripe for enhancement like this.
Personally, I would like to see the interface change to where we could pass in arbitrary element begin/end iterators to set the elements to be searched ( I could use that for some other purposes ).
As for working with ParallelMesh... If you're using MOOSE (which I'm kind of assuming you are) then it's not too bad - we already have an interface where you can specify off-processor elements to be ghosted to the local processor (we use it for contact with ParallelMesh). Just let me know when you're ready and I can show you where those interfaces are.
Just so we're clear: PointLocator is _not_ a "parallel" search: It is a local search that can be wrapped up to do a parallel search. However, I actually recommend just ghosting the region to the local processor that you believe you will need to search so that you can just do pure local searches using PointLocator....