AllOfMP3

[UPDATE: It's not that simple. Apparently, although they are legal strictly speaking, they don't seem to be very fair. Bottom line is - there is a very big chance that the artist you're downloading songs of will not see a dime from it.
I was a little skeptical, so I started Googling with "AllOfMp3 scam". Take a look at one of the results... Look also at this...
I personally intend to liquidate the remaining 10$ or so I have left in my account and I doubt I will renew it. I really don't like the way the music companies extort us with their prices, but that doesn't mean I want to steal the music. I think that a more reasonable pricing should be available. I know some companies have started with new approaches (such as Napster), but they all sell protected files, which is not practical to me.

So I'm back to square one - looking for a good, reliable, legal, not too expensive (and fair) source of digitally available music...]

I’ve discovered this amazing site yesterday. It’s a legal songs download site, and it’s awesome!!! Their pricing makes so much more sense than all the other sites. They charge you by the byte – the larger the file you download, the more you pay. In addition, for most songs you can choose the exact encoding parameters: encoder, bitrate, other encoder-specific parameters. In the end, you end up paying much much less for your songs. You can roughly count on 10 cent/song with 192kbps encoding. Ah, I almost forgot, the download rate I get is over 160KB/s on average.

Did I mention I liked it, A LOT ?!?!

[Update: One thing I think they should improve is their search capabilities. Currently you can only search by artist, album or song. With such an extensive amount of data, I would expect much more flexible and advanced searching options. Hope this will improve over time...]