OK, I went one step ahead and actually purchased some credits there.
They accept payments only via credit card, which involves some heavy lifting for me (I don't own a real credit card and my virtual credit card is prepaid-only and thus not always accepted).
It was a little bit disturbing to go through a credit card processing company from latvia, but after some research I found that AllData is in fact a global business and Latvia is their Eastern Europe/Russia Branch.
Really, there should be more eastern european/russian music shops. Their price levels are so damn low when compared with a typical western income.
So far I purchased 3 full albums. 2 FLAC and 1 MP3/320k (There was no FLAC version of that Album, probably because a physical CD was never actually sold for that album)
The FLAC versions look like real CD rips, the MP3 album is a bit hard to check unless I buy the album from another source again and compare it, but quality is fine.
I've also investigated a bit more as to why they can offer the stuff so cheap and still stay legal:
Melodishop and other eastern european/russian music download shops use a gap in the legislation of these countries.
The reason for that gap lies in the history of collection societies and differences in legislation between "east" and "west".
Collection societies have been responsible for collecting license fees for reproducing music. In the past reproduction was transfering an LP, Cassette or CD to the signal for your radio/tv station's antenna.
For physical CD sales you typically don't need that license as you don't reproduce the music yourself. And the CD manufacturers are typically owned by the labels themselves, so they set the prices high enough.
In the western world, collection societies had to agree on seperate treaties with the music industry when electronic reproduction and distribution were a new business. That's why we have so high prices here.
In the eastern world, the collection societies didn't even think about asking the labels but simply assumed their current legislation already covers all reproduction stuff.
The governments of at least Ukraine and Russia don't care about music licensing and haven't made any attempts to clarify that so far.
Apparently the business of these eastern music shops is not big enough for the major labels to risk a trial on court about this.
Instead they just complain about it in the media and in the press releases from their "ant-illegal copy" lobby organizations. (see here: http://www.iipa.com/rbc/2012/2012SPEC301UKRAINE.PDF
So in fact there is no law against these shops, but it's also not sure if the collection societies may just apply the broadcaster prices to the electronic distribution people until a court decides on that issue.
AllOfMp3 was shut down due to diplomatic influence and I believe pressure on the credit card companies and not due to any court order in russia.
German law says it's legit to buy stuff unless it's from an obviously illegal source. (Obviously illegal doesn't apply here, because you actually PAY them, the payment is backed by your credit card company [PayPal got into the news when they disallowed a major german retailer to sell cuban rum, just because that's illegal in the US] and last but not least they explicitly state that they got a license)
German law also says it's not up to the customer to check whether the retailer has all the necessary licenses as long as it looks fine to a layman.