We basically have to options: 
- Auth with a key used by the Push Server itself. Everybody would have to white list that key to download their own DMs. 
- Change the relay spec to allow a REQ, authed in the past by the user, like on https://github.com/nostr-protocol/nips/pull/1148/ 

 Or maybe DM relays should have their own Push system and each user must set it up in a way that it sends to their NTFY handler when they receive a new one. 

Not as easy as Google Play notifications, but it can work.  

 NTFY has been great and I think the community as a whole should adopt it more heavily