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.
We make heavy use of queue and internal messaging systems. This discussion was solely about the data storage layers, which always causes us more headaches than the messaging/queuing systems.
It's ideal for the counter use-case and with bit of smart thinking you can fit a surprising amount of data into a 32G or 64G machine (and then you can always shard).
Or perhaps I'm missing something?