"Here are a few examples of companies that didn't follow this path (at first)". Note the "at first". Ebay is certainly focused on SEO right now.
The point is that you can get great without SEO-- and companies often do. And the (unspoken) point was that for some companies, search isn't how their products are found.
Low cost distribution is key for startups, but SEO isn't the only way to get that, and often it's a really inefficient way.
If you were starting salesforce.com today, would you hire an SEO specialist among your first 5 hires? Your first 20? How about 37 signals? What percentage of their traffic do you think comes from generalized search (beyond search for their brand name(s)). How about Slide and RockYou? iLike? Do you think SEO should be an early priority for a widget company?
FWIW, I ran a web consultancy for 7 years with a lot of focus on SEO. I'm a big believer in the value of SEO for many types of businesses... Just not all.
Also FWIW, I'm currently running a business that is growing 7-9% per week for the last 16 weeks (that's 3000%+ annual) with no marketing and negligible SEO (virtually all organic search is for a brand name search). We've got some interesting SEO plans, but I maintain that it's a bad thing to focus on for us right now.