You could easily allow a user to see messages ordered by "send time" or "received time". You could even add an "unread" flag to messages, so that unread messages show up first, then migrate to their proper locations in order.
Ya know... kinda like email.
@sp332 You can prevent that by buffering messages. The less you tolerate messages appearing in-between messages you've seen before, the more you buffer. If the latency between your host and the host of someone you follow is high enough that it's taking more than a few seconds for you to get the message, they're effectively down. Late is better than never.
eta: I admit this is a smaller problem for a centralized service than a federated one, but I would argue that it can work "well enough".
Twitter doesn't solve the immediacy problem with any hard guarantees either.
Most of the time email is on par with twitter.
The situ with email is that at any moment the system is up but individual nodes may be unreachable or delayed, conversely if twitter is up all nodes are reachable in constant time, but if it's down all nodes are unreachable.
In real systems these two properties are mean virtually the same thing, at any given point in time your party may or may not be reachable with a given latency.