I would like to see something like this that can scale to 100B+ messages per day (ie. A world scale messaging app), whilst still not revealing who is talking to who.

Clearly the 'send all messages to everyone' approach cannot.

But I wonder if there is an approach that can, with the added complexity that the users use mobile devices and care about battery life and bandwidth usage.

I suspect there is not a design that can still provide anonymity against an attacker who can see all network traffic, but if there is, I'd like to know about it!