I don't download music, but I do know that in WM, at least, you can backup your licenses. You could burn them to cd or a USB drive, then restore them after re-installing Windows.
The problem for me when I purchase music legally from sites like Napster or WalMart is that the license file has to be verified online. If I am travelling with my laptop and do not have a connection, I'm SOL.
Also, as with many Windows users, I reload my computer every 6-12 months just to have a clean start. After I do this, music licenses have to be downloaded from the site where I bought the music and many of them only keep the license for a short period of time.
What if, when I bought a music track, the file was tagged in someway so that it only plays on computers or devices that have my certificate which could be purchased online or free and would include encrypted personal data such as my name or a credit card number. This would allow me to copy the certificate on any of MY devices and allow me to play my music offline. I sure as hell am not going to give my certificate to anyone else. Would something like that work?