The crux of the matter is that you're missing the newspapers motive. They don't want Google to ask their permission, they want google to pay them, which is a huge difference. They DON'T want google to ask for their permission and then delist them from Google News if they had to pay for it.
I am on Google's side on this matter, this sounds like extortion. Google should be free to delist them if they want money from their link, in a capitalist society you should be free to chose who you deal with in your business. I live in France, our government wants to tax google to help the newspapers and they didn't take google's answer (that they'd delist the newspapers) well, because they don't want google to respect their IP and ask for permission, they want Google to pay up no matter what.