When It Comes to SEO, Airbnb Has Some Catching Up to Do
priceonomics.com
priceonomics.com
Remember these guys seeded their growth on Craigslist ads. And now have plenty of cap to advertise across a number of channels. And good products ultimately spread word-of-mouth and repeat usage, so I don't think SEO is something they have to be too worried about.
While I agree with the article that SEO is a complimentary marketing effort they're sagging on, perhaps they're doing so intentionally. If Airbnb had a more traditional hotel-like product then SEO promotion would probably help that product.
But you're right, no startup ever said that!