>The traffic needed to maintain presence scales by N^2

Only true if we assume the average number of contacts scales linearly with the total number of users, right? But then, we could also assume that the average number of messages that a given user sends scales linearly with the total number of users, in which case the amount of traffic needed to transmit messages also scales by N^2.

A couple of easy fixes: cap the number of contacts at some large constant (as many services do), or just disable presence information altogether in your implementation. I'm skeptical that this played a major role in XMPP's lack of popularity, especially because e.g. WhatsApp and Facebook Messenger have presence information, and are still popular.