Well, this passage from the last paragraph of the Wikipedia entry for AllOfMP3 is all I need:
"The
legal status of ALLOFMP3 has been discussed extensively at FADMINE, which comes to the conclusion that the site is indeed legal in the U.S. and Russia. Foremost proof is that the RIAA has targeted companies who resell songs bought from ALLOFMP3, but ignore and condone ALLOFMP3."
If you follow that link, it's got some convincing and well-researched (though admittedly not 100% conclusive) arguments that AllOfMP3 isn't just an illegal site the RIAA isn't going after, it's a legal service. Now, obviously, you'd think RIAA would be considering ways to change their arrangement with Russia to close this loophole, but as long as that loophole exists, I'm happy to use it to my advantage.