De La Soul situation is a little more complicated. Many of their albums used uncleared samples and some of the rights are still unclear. That's also why their stuff isn't on iTunes..

But streaming services are so much handier, thanks to their large catalogs. I use Google Play Music and used the free matching/upload functionality to upload my Beatles, De La Soul, and John Zorn collection :).

So this means you can now import the entire De La Soul catalog into Spotify and only have The Beatles left as a reason for not using it!

Plenty of music not on spotify because their deal is frankly whack.