This is a very interesting question. Forewarning, there will definitely be an amount of personal opinion I reference here, but it is my experience and I believe it to be valid.
You're talking about the classic problem of improving a service. As humans, we've been inventing and improving our lives for centuries.
Ask yourself this one question - what would happen if we never re-invented the wheel.
Personally, I didn't know much about Airbnb except that they were basic travel rental locations. A short big of research leads me to their slogan
Start Your Adventure
Discover destinations that travelers love.
The need here that was not being met could have been a variety of things, but most likely was the unique services in each location. This was confirmed when I tried to click a listing:
With Airbnb, you can find unique accommodations in people's homes—from
houses and apartments, to tree houses and igloos. The listing details
below explain what you'll find in this space. If you have any
questions, you can contact the host directly.
Clearly, Airbnb prides itself on unique, creative travel lodging that really gives the traveler a dive into culture with a sense of security and reliability. You get to see how people live in different cultures.
Furthermore, it seems to me Airbnb is somewhat of a luxury good - meaning people might not need it, but they want it badly enough to pay for it as if they needed it.
I hope that addresses your question. Luxury goods can often be harder to think about, given that people don't really need them (I mean, come on, commercial flights to the moon?), yet they still can be actively traded as if they were necessities.
From the startup sense, that's about as far as I need to go, but you may want to look into some economic theory if you want to learn more about the behavior of different goods.
EDIT: Apparently Airbnb also operates to reduce the costs between the home space seller (getting cash for unused space) and the costs paid by the person looking for a place to stay. In that sense, it's taking the concept of arbitrage and giving a smaller margin (the big companies love big margins!) such that everybody is still happy (except for the big companies, clearly).
This is the same concept as being used by the crowd-sourcing taxi services (like Uber and Lyft) - effectively causing the same damage with the large-margin security of taxi drivers.
In reality, though, it's competition at its best. Play the game or become useless. Or complain to the government until they make an extremely poor decision to prolong a bad system).