I've been using Amazon because their MP3s are drm-free, but now I'm curious are there any music-resellers that have distribute drm-free, and have a decent policy that in the event of data-loss I can redownload my legally purchased music?
I've bought from 7digital in the past. They provide tracks in DRM-free MP3 as well as AAC and WMA. There is a "Locker" where you can redownload songs that you've previously purchased.
Also, http://thesixtyone.com allows it.
Magnatune.com meets your criteria. They offer you convenient redownload links, do not use any DRM, and even don't mind if you give those redownload links to some of your friends.
Well, since today, Amazon provides a backup service called Cloud Drive :
Purchase a song or album from the Amazon MP3 Store and click the Save to Amazon Cloud Drive button when your purchase is complete. Your purchase will be saved for free.
Start with 5 GB of free Cloud Drive storage. Upgrade to 20 GB with an MP3 album purchase (see details). Use Cloud Player to browse and search your library, create playlists, and download to your computer.
More infos on the annoucement page