IIRC when spotify started it was only available in sweden and was classed as a pseudo-radio which allowed them to get a blanket deal with Swedish Performing Rights Society (STIM) which governs radio/public music license payments for sweden. It also was a case of the record labels being more willing to try this out in a smaller market before committing globally.

I remember using it 2007-2008-ish and it being pretty magical at the time.

Worked on a product like spotify many years ago, just to chime in that jonorourke is right. I think we had 4 major deals with the labels (Universal, Sony, WB and one I can't remember), and then just a few deals with some smaller labels which to be honest, weren't really important for the userbase/revenue (sure you may want Beethoven's 5th played by the Czech Symphony on the London Hall, but 99.9999% of the users just wanted to listen to the stuff from the major 4)