Why shouldn't streaming services pay more?
The service is of higher value to customers, so why do they expect to pay less for the input materials?
A single song played on a radio station has a limited geographical reach and uncertain audience - not everyone who can receive it does receive it, and there's no way to know. That uncertainty is why radio stations get discounted rates. But in a streaming service, you know exactly how many people could hear the song, and the nature of Pandora means that the people who did hear it are more likely to have wanted to - that's a higher value to the customer, and it reduces the chance of that customer buying the song if they can hear it as often as they want on the stream.
Let's turn around one of the standard arguments on this subject for a moment:
If Pandora aren't able to make money in the reality that's in place, they should look at other streams of income: Promotions, placement, advertising. After all, it's what musicians have been told to do in response to diminishing royalties. Why doesn't it apply to businesses, too?
It'd be nice if the usual suspects looked past "The Man" being involved, and examined the situation a bit more rationally. The royalty payment in question here is for the songwriters. Many songwriters rely entirely on royalties for their income, and because "songwriter" is not the same thing as "performer", the option of going on tour or selling t-shirts isn't open to them.
Okay, a higher royalty means more money skimmed off by the collection agency, but it's only a small skim in this case, and it means more money for the person who actually wrote the song.
To take an example of a different creative endeavour: Why is okay to give Google or Apple 30% every time you buy an app from a developer, but not okay to give the collection agency 1c every time the songwriter gets 10c? (and you didn't even have to pay that 11c!). In both cases, you're paying middlemen, but both are providing the service of collecting and distributing revenue for the creators. (That 30% isn't paying for hosting; most of the costs in running an appstore are in user administration, accounting and payment processing.)