http://www.deezer.com/This is generating some interest on slashdot today, they run out of France where the environment is obviously a little more hospitable to this kind of service (compare it with Pandora).
"Our concept is simple:
-Give consumers a full and free access to all their favourite songs
-Pay artists and their producers through a revenue share based on our advertising revenues
- Help discovering new artists through a wide audience"
Once you've made an account you can search for music and add it to a playlist kept on their server to listen to... enjoy!
I'm hoping this is going to stop me downloading music before I buy it to see if I like it.