> "I can’t even leave feedback... as we never got to stay there."

I think this is a bigger deal than the cancellation -- the fact that, on a site that's all about reputation, there's no reputation hit for a host canceling someone's rental. Airbnb should create a feedback system that allows feedback to be given for various steps of the process, not just the stay itself.