For a notification-heavy app, I'm surprised at the lack of consideration given to Queue/Topic Messaging servers. 5B notifications/month isn't quite 2k/s, which really isn't all that onerous. Routing within messaging apps would seem like a natural fit.
Or perhaps I'm missing something?