The whole business may have changed quite much over there years. Back in the days you had your own people driving around, know you can crowd source quite much of the data collection. When you have the location data for millions of people, you can for example figure out where the roads go, make good guesses about speed limits and figure out one way streets. Points of interest can be mined from web. From search logs you can probably see if you are missing some addresses.

So? Alta Vista was in the search business long before Google was a PhD thesis.