The right solution is to have every single push notification have a "Silence this" link on it. That takes you to a screen naming the app and asking if you want to turn off its ability to do push notifications. This fact is tracked across users.

Add a warning from Apple that any app that is turned off by too many people will be deemed to be too spammy, and taken out of the app store.

This would completely solve the problem. In the absence of any such mechanism, all incentives point towards continued abuse of the feature.