Nobody stores all shortest paths, that's just silly. With some rather simple preprocessing you can answer shortest paths queries on the US road network in microseconds [1], with preprocessing time of less than a day on a single machine. Surely Google can scale that up to larger graphs.

[1]http://people.mpi-inf.mpg.de/~dmatijev/papers/DIMACS06.pdf