The metadata is all you need: find a few messages in an interesting e2e chat, ask Apple which accounts received push notifications at those specific times, find intersection.
I’m not sure how E2EE would work for notifications. The ISV sends the notification but the OS displays it. I suppose some key exchange between each ISV and each device?
My understanding is that Pushover encrypts the message with your device's public key (from the app) and delivers it through Apple/Google. On iOS you need a special permission from Apple to "filter" push notifications and this is the hook they use to capture and decrypt it before displaying it on your phone