Where does the iPhone store deleted apps' notification settings?
Apparently, Push Notifications Permission are reset if the devices are restored or the app is uninstalled for a day.

Extracted from Apple's Technical Note:


  The first time a push-enabled app registers for push notifications, iOS asks the user if they wish to receive notifications for that app. Once the user has responded to this alert it is not presented again unless the device is restored or the app has been uninstalled for at least a day.


Therefore, these preferences must be stored where iOS System Settings are stored.