Charging developers is probably going to result in the opposite of what you want: notifying the user of something useful probably monetizes far less than the spammy notifications instead.

Apple just needs to get a grip and start swinging banhammers, like Facebook did with Zynga. Put troublesome apps in a probation period, where notification strings end up going through an approval process. And punish developers by holding subsequent apps up in the review process.