Yes they started in USA, but when UK was announced it wasn't a blank map (like OSM was when it started). The UK maps started with purchased, non-free data. So in a way, you need to bootstrap it somehow.
It all started with public data. Google was born out of a project at Stanford centered around the idea of "online libraries". They had lots of practice using public datasets. The crawlable web is itself a public dataset.
Your point about OSM is the reason I mentioned the generosity of MapQuest.