So a P2er showed me this: AllofMP3.com. It's a legal-mp3-download site based in Russia - so you can buy your music (lots of it American and European) by importing it - and not importing into a library, I mean importing from overseas. It follows Russia's copyright law and you're paying for your music - the 'unlimited download' rate comes out to $10 per GB of music, and you can choose the bitrate at which you download (anywhere from 128 to 392 I believe. I searched for a handful of popular artists I like and I got some pretty decent results: most of the really good artists (BT, Orbital, etc) don't have complete collections, but the albums they do have are complete.
So, if you want a cheap alternative to iTunes and like MP3s, give it a shot.