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.
What was the date they started in the UK? How much cash on hand did they have at that point? A billion or so in the bank maybe?
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.
