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.