Protocol
Yes, this is going to sound like a cop-out but it's really up to you. Honestly, what you've described sounds a heck of a lot like IRC, but XMPP is quite extensible and widely used, so it's probably the easiest non-IRC to get working and to get support for. You're going to be able to find a lot of examples for both platforms, and likely even already-prepared libraries, if you want to go that direction. I'm not going to go recommend any, but a quick search should be a very useful tool here. There's no one right answer, but XMPP is certainly not a bad choice.
Cloud Service
Both Azure and AWS are very good services. A lot of high-profile or important applications run on each of them. One of the reasons I tend to favor Azure over AWS, however, is that Microsoft really tries to make it easy for you to get it. If you haven't yet, I would look into Bizspark, which, if you get approved for, will give you, among other things, a free small instance of Azure. To be fair, Amazon does the same kind of thing, but they seem to give you a little bit less, and only for a year (Bizspark is for 3 years). On the other hand, Bizspark actually requires that you get approved, while Amazon really just gives it to you pretty easily.
All in all, either is really a good service to go with, and both Microsoft and Amazon tend to be very committed to helping developers get things done, so you can't go wrong either way. The best way of deciding is to look at the features they offer compared to what you need, and the pricing for your minimum and ideal levels. For example, if you did want to support Windows Phone, Azure might be a better option, because they work well together, but if you wanted to leverage fulfilment services and ship tshirts or coffee mugs or anything like that in connection, Amazon might be the better choice (Note: Don't read into either of these; I purposely picked two scenarios that you didn't mention just to give an example of some of the unique features of the services.)
As for the Elastic Load Balancing and Auto Scaling, that's just AWS branding what cloud servers in general do. All decent cloud services will make scaling your system technologically negligible, at least from their side (if you happen to have bad code that doesn't scale well, you can't really blame it on them...). So yes, those are good things, but everyone has them, so they shouldn't be a decision maker.
Best Answer
While I won't claim enough experience with either environment to answer your question fully, if you're considering Clojure on GAE you may find appengine-magic useful:
https://github.com/gcv/appengine-magic
As an aside, the database limitations, performance, and costs are worth looking at closely with either platform, and may convince you (as it did me) to avoid both. For example, see these stories: