Qtrax: new free, legal music downloads! Supported by advertising...
From what I read (have to see if I can find the link), I think Sony had a deal in place previously, but it was a different incarnation of the software.. The deal has since expired..
I think maybe the music industry got cold feet at the last minute.. They've fought this thing for so long that they don't want to relinquish control yet..