Have you tried a subscription service? They're pretty amazing. You can play whatever you want. It's unlimited access to music and (if it works correctly) just as good as having it stored locally.
I have tried Napster actually. I agree, it is a great service for some users... There were lots of problems with it for me. First of all, the range of available music was very limited. New, popular stuff abounded, but back catalogs and indie tracks are still much easier to find on Gnutella. Plus, I'm (I admit) somewhat philosophically opposed to renting much of anything. The "purchase" options in Napster were even more crippled and broken.
Plus, it just wasn't flexible enough. If I
buy a song, I want to be able to play it on whatever platform I want (Linux, OSX, my MP3 CD Player, my Car CD player, or my wife's iPod). I also want to be able to use it for a soundtrack in my
home movies created using Final Cut Pro. I also need to be able to re-sell it when I no longer want it (I don't care how they handle forcing me to give up my copies). If there was a DRM format that easily allowed me to do all of that, without violating the DMCA, I'd be happy. Until then....
Oh, and switching to another service assumes that the pricing problem isn't caused by the record companies themselves. If it is (and keep in mind, these people have already been found guilty of price fixing and collusion once), then what choice will I have? If the RIAA member companies all raise their rates (and they've certainly indicated they'd like to -- where it comes to iTunes at least), then ALL of the "rental" services will have to raise theirs.
At least with CDs I can buy used, or just keep listening to the music I already have!
Just switching to a different service would work if the free market economy really worked in the entertainment business. Unfortunately, the RIAA member companies operate (more often than not) as a single entity, creating an effective monopoly.
That's why I said that a shake/break up would help. It would help quality of product, pricing, and quality of service.