On a whim I had a little play with AllofMp3.com last night (when you sign up you get $0.50 credit to play with). Now when I originally heard of this service my main thoughts was why anyone would pay for something thats so legally dubious, especially as it's not exactly hard to get music for free. Legality aside the user experience is quite good. The site is easy to navigate, the samples are pretty long (and don't require Realplayer to listen to) and the selection is comprehensive. However the thing I liked most was the media options your offered. There is no DRM'ed formats and you can choose between mp3, ogg, mpc or mpeg-4 encoding and a choice of bitrate. Once you click order it goes and encodes the file for you there and then. The actual charge is based on final file size so the lower quality encoding the cheaper it is. I'm not sure how close to the normal track price a full quality (lossless) file is but I suspect its on a parity to a cheap CD price.
Of course this sort of flexibility and value for money probably won't catch on. With more and more CD's getting the DRM treatment I guess I'll just have to buy less music and listen to my back catalog or find alternative sources of music.