The service will only have 100,000 songs, so they must have struck some special deal with some labels to allow them to do that.
When people ask me why Magnatune "is important" I tell them that it's because eventually the whole online music space will adopt much of what Magnatune does, just as the software industry changed its practice because of shareware & small publishers over the past 20 years.
The reason: no DRM, listen-before-buying, full-quality-downloads, and selling a no-evil product are all competitive advantages, and in an efficient market (which we're slowly getting) these competitive advantages win out.
So... Yahoo Japan will have "try before you buy" ... I'll be that if the feature does well in Japan, they'll introduce it at the USA version of Yahoo Music.