[willrobinson]

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.