New Site ALLOFMP3 offers to download MP3, sans DRM, not by the tune, but the the kilo (byte). One can fetch from the 250,000 titles available buy paying 1 euro cent per MB.
This Site, hosted in Russia, obtained the appropriate distribution rights there, playing with an apparently obscure point in the Russian copyrights laws. This would probably not be legal in France, for instance.