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.
For a graphical illustration of the history of the word spam, check out this google ngram search: http://books.google.com/ngrams/graph?content=spam%2Cjunk+mai.... I started it at 1930 b/c I thought it was kind of fun to see the spike around the time that Hormel introduced the other sort of Spam.