[fmajid]

There are systems like MIT's Alpenhorn and Vuvuzela that protect metadata like push notifications by using encryption and deliberately adding noise to foil traffic analysis. Notably both sender and receiver are kept private and you do not need an out-of-band key exchange mechanism to initiate communications for the first time.

[sliken]

I've wondered if signal would be more secure if each signal account periodically sent a message to another signal message. The client would of course decrypt, notice it's just a fake/noise message, reply to it, and then delete it.

[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?