There's only a couple Hollywood Video stores here in Birmingham, but fortunately, one is directly on my drive to work every morning. I typically use them. The selection at the store I use blows every other B&M store I've ever been to out of the water and their rental policies are pretty decent IMO. 5 day rentals for everything and $1 off your next rental on new releases if you return it the next day (which I usually do.)
I tried Netflix and can see the allure from a pure movies-per-dollar perspective, especially for those who watch gobs of movies or are into pirating. But to me, movie rentals are definitely an immediate gratification based purchase. The biggest thing I didn't like about Netflix was that you might be all ready to watch a particularly movie, but you had to wait several days before your old videos were processed back into the system and they ship you your next round. By that time I might not really want to see that particular movie because I might be in the mood for something else. You've theoretically got 'unlimited' rentals, but you're held hostage to a system with a good bit of lag time.