No, they don't, for the same reason I outlined above with the library example.
I don't understand why this confuses people so much.
The video store rents authorized copies of copyrighted works. Each video on that shelf is is a single licensed copy, lawfully acquired. The video store can do whatever it wants with that piece of plastic.
What it CAN'T do is make and distribute a new, unauthorized copy. But that's precisely what happens on Kazaa -- millions of new, unauthorized copies being made and distributed every day, without permission from the copyright holders.
The difference between online downloading and the video store (or library) is very simple: One is copyright infringement, the other is not.