It is about impossible to get a marketplace going from a standing start. I've commented on it before elsewhere: picking off Craigslist users was always critical for Airbnb to get going. There are dozens of startups trying to build companies off the back of what Craigslist doesn't provide.
I'm sure the Airbnb guys probably started with the honest approach, realized it got them nothing but cease and desist notes, so switched to the craftier fake emails from girls interested in the well-being of vacation renters everywhere. I bet it felt icky at the time, but here they are. And "you know what's cool....?"