Scale covers lots of things, including statefull v. stateless and (appropriate to this discussion) asynchronous comms and the ability to queue requests. Scale in that sense is facilitated by retrying a remote call that failed - possibly because the server is at capacity. That implies store/forward, which is what the "queue" part of message queuing does. You can definitely use tools like ZeroMQ, MQ Series, MSMQ or WCF to achieve that. You can also use a database table with a flag indicating whether a message was delivered or not (ref. my link above).

Not quite sure what HTTP has to do with message queuing, other than being a protocol one might use. If scale is so important, perf is a concern, in which case UDP would be a consideration. Would I go down that road? Doubt it, because I suspect the acceptable answer lies somewhere between HTTP and UDP, and I also suspect that better gains can be made by optimising end-to-end throughout and solution design rather than worrying about the semantics of a protocol. What's the benefit, for example, of streaming data over a TCP connection when that data is XML? TLV or some other binary format will serve you a lot better.

Final words on scale - asynchronous delivery (such as message queuing) is one technique. Another is to scale servers out and/or up. Also, as already mentioned, server state and of course pipeline/routing efficiency. Whilst I stand by what I said, I've not had the opportunity to work at the scale you have, so I'd love to know what problems you've encountered when scaling to millions of nodes.