That's what emusic does. The problem is the copyright holder would have to agree to let them do this (they can't just send a check to columbia and say it's all good) So I doubt there will ever be anything from a major record company on there.

Emusic is great for 10 USD a month.