AllofMp3.com existed because of a loophole in Russian Law. The loophole allowed the Russian version of the RIAA (called the ROM IIRC) to collect whatever fees it wanted for artists, even without the artists consent or knowledge, so technically it WAS legal in Russia. This technically only applied to Russian citizens, but the Internet doesn't follow national boundaries, so it was a free for all. The law was only recently changed since the Russians want to gain entrance into the World Trade Organization (WTO). They were pressured into changing their law and closing the loophole by the US and EU and their lobbying groups backed by, you guessed it, the RIAA. The real blow was dealt to them when first VISA and then MASTERCARD stopped doing business with them, again pressured by the RIAA.
Oddly, there is still a loophole there and another site has popped up and taken AllOfMp3.com's music/servers over and moved them, supposedly, to Moscow where it is still legal.
Never underestimate the power of the RIAA and their cronies to subvert or downright change the laws of any country to suit them.
For those thinking the music was crap or a virus, it was neither. You could get a choice of bit-rates (96k to 320k and in some cases lossless) for a sliding price scale and the quality was overall quite good. No Viruses, no Spyware, or anything of the kind. I had let my account laps some years ago so it has been a while since I was there.