[Kon-Peki]

Somebody, somewhere has map the fact that user ABC wants their push notifications delivered to device XYZ. That somebody will always respond to legal requests demanding information about this mapping, and keep it secret if legally required.

Nobody is going to break the law on your behalf. Nobody. Not even this smug email provider who did what they did because they didn't want Google to have metadata.

Developer documentation has stated, from the very beginning, not to put sensitive info into push notifications. If you absolutely must, encrypt it with a key that they don't have. An ideal push notification is "Hi", and the app should know what to do with that. Whatever shows up on your phone screen was generated entirely on your phone and isn't sent to any server, and can't be recovered using these legal requests. Unless the app developer is stupid, in which case why would you think that another service is going to change that fact?