[harimau]

>Correct, some of my best results were from just talking to people about finding a place, knocking on doors, etc.

That's the benefit of doing the hostel thing and talking with people that have been where you're going. Some will say what's in your LP and some might have other suggestions. The staff as well -- they might have friends in another city or tell you where they stay, bc it's cheaper for them, and maybe hook you up.

There's also the AirBnB w/o paying: couchsurfing.org - which has been around a while.

personlurking mentioned Portugal - it's been a while but when I was in the Algarve during a summer trip there tended to be some little old ladies always letting their places out. They looked quite nice and, if you were staying a week or more, were reasonably priced. Even better if you find some companions.