Spotify, and all other legal digital streaming or download services, rely on the correct owning label uploading the audio and detailed label copy info to Spotify for the music to be available. for many labels that simply don't exist any more or where they haven't reached agreement with particular artists over digital royalties and distribution, this material simply won't be available anywhere legally.

As Dub said, the royalties return for the vast majority of artist and labels from services like Spotify (and even youtube) is currently so small its hardly worth the bother in some cases. it is a lot of complicated work to get it sorted, especially for bigger catalogues and artists seem to think that its worth a lot more than it is so sometimes demand large one-off fees to allow it to happen anyway. but labels, big and small, are all going through their catalogue to get as much available as possible so it will get better all the time

as for Spotify itself. its very early days for them in their big plan, but it seems to be working at the moment. they have financial backing from the major labels, and more importantly they're working together to get as much available as possible. they can potentially charge quite a lot for targeted ads, but you're all gonna have to get used to the choice of ads funding your music listening, or paying for it yourself for systems like this as the running costs are still quite high. I went premium last month, the sound quality is much better especially as I listen at work with headphones, and the lack of ads is worth it for me, for now. this model is known as Freemium, and they probably need between 5-10% of people to pay for the premium service to help fund the others together with advertising. I think that a tenner a month is great value but they could get a lot more subscribers if they bring it down a bit

there is an interesting, if long interview with the founder of Spotify here

http://www.arcticstartup.com/2009/09/21/interview-with-daniel-ek-of-spotify/

annoyingly, he is only like 26!