I may be wrong, but at least here in Germany I'm pretty sure the unavailability of spotify, rdio and so on can't be explained with major labels refusing to allow those service here. No, when it comes to germany you have to look at the media right organisation GEMA that seems to demand unreasonable high fees from streaming services. There is an ongoing dispute between the GEMA and Google concerning Youtube, which is why you will see a lot of videos that are "unavailable in your region".
It seems as if at this point these companies aren't even bothering to negogiate with the GEMA anymore. I can't see why labels would refuse to offer their content here.