The problem is that the labels (much like Hollywood film studios) are clinging to an outdated business model and screwing us all in the process. There might have been a time when licensing content based on geographical region made sense; That time is long gone. When I go to a streaming website and am told I can't use it because of my IP prefix, I don't see a rights-holder making a fair licensing agreement, I see a bunch of clueless old rich dudes mumbling about "kids these days, with their digital doo-hickeys and global mumbo-jumbo."
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.