I think the most important property to preserve is causality; that is, if a user sends a message B after they have read (i.e., received) a message A, then B should come after A for everyone, because B depends on A. Basically use a Lamport clock.