OK but I still don't see the problem. Even with a fully decentralized system where the servers are just pure relays with no authority, you have two options:
1. Display messages in the order in which they claim to have been sent, or
2. Display messages in the order of arrival
Case #2 is the obvious/uninteresting one, there's nothing to say about it.
Case #1 is what people are saying is so impossible to achieve a global order for, but really, what's the big deal? If a client claims to have sent a message at an unusual time (say, > 10 seconds in the past, or after the app was already quit, or whatever criteria you want to set), then just insert it at that point in the conversation, and visually indicate to the user the discrepancy. And clock skews won't really be much of a problem because messages can easily indicate prior messages in the conversation, so that a mere clock skew doesn't insert them before preceding messages.
What's so hard to make user-friendly/intuitive here?