The US Gov also provide lots of geographical data for free including place name for the whole world at : http://geonames.nga.mil/gns/html/namefiles.html
I dont know if this is up to the level of detail you seek but that could be a good starting point (for exemple Netherlands data contain 22887 record).
I download and have a quick look to some place I know, the locations are not very accurate (could be off to 100 or 1000 meters sometime) but it seem to have most of city, town, hamlet and small populated place as well as a lot of non populated place like mountain, rivers, forest, name of point of interest and other geographical feature. I would say it is as complete as what google map display if not more complete (of course disregarding street name/adresses...) for the small area I checked.
So to answer your question most map service probably get their name data from US National Geospatial-Intelligence Agency who give it freely for the whole world (Some other country have similar database, sometime in open data sometime to buy, but generally they covers only their national territories)