To be honest I probably much for a music download service as I'm not really a big customer of the music industry. That being said if this included both video and software I would gladly pay around €25 a month. Although for me that would probably signify a cut in the amount I spend in a month, and provided the service was good enough (high quality encodes, no drm, the ability to watch on whatever I wanted whenever I wanted - I would probably be willing to pay up to €40 a month)
I think the existance of sites like rapidshare and their ilk prove that, not only is it possible to compete with free (after all they are competing with torrents), but people are willing to pay something for what they consume. Obviously a legal equivilent would need to charge more than whatever rapidshare charge a month, but the largest cost with download services must be bandwidth and a p2p service would avoid that, so possibly they wouldn't have to charge all that much.
I think a far more interesting question to as is if it is possible for the creative industries to make money with a service like this. Honestly I suspect it is, but they really need to start looking at this to see if it is. After all, if the executives in the music industry can't figure out a way to make money off of music, then they really shouldn't be executives in the music industry to start with.