I think VCs would have understood the potential better if they were sparebedroom.com instead of airbnb.com.
The founders literally rented an airbed in their apartment, which spawned their idea to create the service and inspired the name, but I don't know that they ever set out to create a marketplace for specifically this.
I could be wrong but nothing I've ever heard them say has suggested this was the idea, even in the company's very early days. Indeed I believe their early niche was renting out space for conference goers, in the homes of like-minded individuals, not renting specifically airbeds for conference goers - that'd be a bit absurdly niche, no?
What AirBNB has executed brilliantly are:
1. They offer the complete booking workflow: from initial contact to payment. They also offer feedbacks, reviews, rating, etc. to make the whole marketplace more credible.
2. They bootstrapped the market really well. Some of the early tactics were shady, but well, that's what you can do when you are a small start up. Offering free professional photographer service to the owner was a very good move: much better than spending that money on SEM or other marketing ploys.
3. A lot of luck.
N.B. I'm currently travelling and using Airbnb almost exclusively for accommodation, if that's somehow relevant.
Airbnb seems to have become the cliche example of a 'crazy idea' that turns into a unicorn and, honestly, I struggle to see why people think the idea, per se, was crazy or groundbreaking.
It's not a crazy idea. In fact it's a very natural, obvious idea, that has existed forever. People have rented, and sub-let, rooms for decades. The problem has always been high barrier to entry (on both sides) and therefore low liquidity in the market, such that short term 'holiday' type lets are too much of a hassle to be tenable, and only longer term lets have been feasible.
The idea has always been there, what's not really been there until Airbnb, and what is their remarkable achievement, is the building of a singular, reputable, trustworthy, easily accessible marketplace for this, to get the liquidity to where it needs to be to be workable.
It's the execution on this, not the idea itself, that's the remarkable thing. If it was such a crazy idea, it would have taken much, much longer (+10 years perhaps) to have truly caught on. The fact that they've had such rapid growth points to the fact that a lot of hosts and travellers were ready for it and just waiting for the opportunity to take part in the short term lets marketplace.