Then I would just say, XMPP is new and fancy, but consider the old fashioned stateless HTTP interface. When I was implementing my own service, I was worried Google is not going to handle the load. Since we were partners with Google for a good while I was able to climb the ladder of people to get an answer, and plow through their closed-door policy for questions such as "Will you guys handle this load? (5M msg/min)". I wrote a huge email explaining every edge case and what I'm doing. The answer was "We will handle it.". No detail, no context, no buts. I wasn't confident at all. But in the end, they did handle it :)
For example, workers could discard messages older than some threshold, quickly emptying the queue if there are expired messages. Clients might not even queue messages if the queue is currently too long, perhaps even providing a convenient signal for them to back off from their most chatty behaviour.
Some messages will not be delivered on time if there is significant backpressure. There is not much you can do about it, apart from avoiding choking yourself.
Perhaps the queue could work with a LIFO policy, to help at least some messages go through in time instead of having most messaged delayed near to the expiration threshold.
This service buffers potential pushes for all users being messages, that then watches the presence system to determine if they are on their desktop or mobile (this is millions of presence watchers and 10s of millions of buffered messages), and users are constantly clearing these buffers by reading on the clients and finally when a user is offline or goes offline we emit their pushes to them (which is what this article talks about). This service was evolved from our push system from the game we worked on and when it just did pushes only and no other logic it could push at 1m/sec in batches, but its responsibility has changed.
Context matters :)