I've never used AirBnB and have no real plans to. However, I have traveled around Europe extensively, and some of the best times were when I simply arrived somewhere and then attempted to find accommodation.
I rode my motorcycle from London to Spain, toured for two weeks and never booked a single hotel in advance (my GPS packed it in on the second day too, so I played with paper maps). Only once was the first hotel I entered unable to find me a room.
I traveled around Sicily on public transport, mostly buses, a few trains and ferries. Again, I never booked accommodation in advance, always found somewhere and was never stranded.