Just saw this: http://www.umixitmusic.com/
Basically, it provides you with the isolated audio tracks of a song, along with mixing software. Don't like the guitar solo? Record your own!
I haven't tried it yet, but I'm betting I will soon. The only technical downside I see at the moment is that you can only export your song in 128KBPS WMA. I prefer higher bitrate encodings, thank you.
Hopefully this concept will take off, and the owning companies won't try to nickel and dime us too much.