Before we get into arguments about the validity of libertarianism...I think it shouldn't be shocking that when a company becomes large (with more at stake), they have to act in ways that will be overbearing in comparison to what they were before.
The quoted complaint above could easily apply to, let's say, the Apple iOS store, in which decisions are made heavily in favor of playing it safe and clean. I would like to argue that I'm wise enough to make my own choices about downloading immoral/unpleasant apps...and I'm entitled to make that argument. However, I can't argue that this...ahem, proactive policy prevents a great many shit-fests that might otherwise arise were it not in place. And I really can't dispute that Apple so far been wildly successful in the app marketplace.
Likewise, from Airbnb's perspective, I can see why they've made the calculation that proactively preventing scammers is overall, a good business decision. Because a few disasters from slightly foolish customers is enough to doom the entire ship.