AllofMp3.com is not a legal service either in Russia or anywhere else. It is distributing music without any permission from the artists or copyright holders. Unlike all the legitimate sites, it does not pay artists or copyright holders so it is effectively stealing from those who create music. Like most things that appear to be too good to be true, allofmp3.com is not what it seems.
There is not much question that the service isn't legal outside of Russia. But AllofMp3.com is correct in asserting that
The site AllOfMP3.com belongs to a Russian company and for 6 years it has operated within the country, in full compliance with all Russian laws. Throughout this period the various government offices have scrutinized site's legality and have not found any breach of the law. So far there has been no decision by any Russian court contesting the site's legality.
Sadly there is little doubt that they will soon be shut down as part of the price for Russia joining the WTO.