Spam does not mean unsolicited marketing. Door-to-door sales, direct mail, telemarketing, billboards - even the guy who in every tourist trap in the world who begs you to come eat at his restaurant - are all unsolicited marketing, but not spam. Spam refers to bulk-generated, unsolicited marketing over electronic mediums.
The distinction is important, because in non-electronic mediums, the conversion threshold for unsolicited marketing is high enough that the market more or less self-regulates. Email, or electronic mediums broadly, became a new territory because the CPM of unsolicited messages effectively went to zero, meaning all but the lowest conversion rates would generate positive ROI.
As such, sending strangers unsolicited messages about new services over email, twitter, etc is legit, as long as you are doing so manually and are not deceiving them. I have no idea what the AirBNB folks did, but I suspect that it was manual.