Amazon MP3 Store
Too late for Talk Like A Pirate Day, Amazon recently unleased their MP3 store, as well covered by Ars Technica:
There are a few restrictions. One of the biggest is that there's no redownloading of tracks; you'd better make a backup, because if you lose a song, you'll have to purchase it again to get another copy.
Spotty selection, especially in the esoteric (and not so esoteric) classical section, though much of that has to do with music labels refusing MP3 sales. Went on a mostly Beethoven spree, having somehow never added the Diabelli Variations nor Missa Solemnis to my collection.