Personally I love using Amazon MP3, it works great at least for me. Provides great bitrate on sound quality. Prices seem to be very par and even cheaper some times then itunes. The other nice thing is it can be used through the phone, with the Amazon MP3 app.
I looked at Amazon MP3, that will work. Only issue is that when I search for a group/artist I get songs with that name too, not just the group/artist. For example, The Doors. It also lists song with "doors" in the title.