Given an arbitrary pair of origin & destination, how do I design a system that can effectively query all paths that cross the pair from a GPS dataset?
A DB with spatial capabilities built-in should be able to do that. One option would be PostGIS. Check out this link for example queries using it.