They buy different starting data sets.
I guess most services also use things like the free GNIS data set from the U.S. government (it has good coverage, but the geocoding is not amazing).
Edit: And an entity like GNIS actually has less resources than Foursquare gets with its army of users (or at least, a lot less feedback generation).