This shouldn't be an issue for systems where a server mediates communication: the server should be timestamping messages, not the clients. This could indeed be

This shouldn't be an issue for systems where a server mediates communication: the server should be timestamping messages, not the clients. This could indeed be a potential problem for a decentralized system, or one where the server for some reason cannot (or cannot be trusted to) timestamp messages. In that case, I think the best behavior for a client would be to always display messages in the order they've arrived, regardless of any timestamp provided by the sender. But this problem shouldn't exist for a system like Matrix. Matrix is (somewhat) decentralized, but each homeserver can still decide on the message ordering it will present to its own clients.