I don't think this is really a problem, at least in the case of client->homeserver connections. The homeserver should not be trusting the client's sent timestamp. The homeserver should consider the message sent at the time it receives it, and the client should know this and update the sent timestamp displayed to the user when it is finally able to connect to the homeserver, and the homeserver acknowledges receipt of the message.

The bigger problem is how to handle homeserver<->homeserver comms. My initial feeling is that the homeserver where a destination room is hosted (let's call this one "A") should have the final say, and if there are people on another homeserver ("B") that have joined the room, and are chatting while there's a break in connectivity between the two homeservers, then A should just append all the messages from B to the end of the record (with correspondingly "later" timestamps) to the "official" record, when B is able to communicate with A again.

But this feels messy too; presumably all of those new messages (a conversation that may have been going on for tens of minutes or hours) would be smooshed in to have their timestamps all appear nearly at the same time? No, that's not great either.

Or perhaps B just shouldn't accept messages for that room while it can't communicate with A? That doesn't seem great either.

Then instead imagine this: the user really is innocent and just happened to coincidentally send the message right after the start of a long period of poor connectivity (like a flight, or a road trip, etc). If you just allow it to go through after an arbitrary delay, with only a log of the received time for liability purposes, then the user wouldn't have any indication of this scenario occurring.

Wouldn't it be better in that case to show an error so that they can make sure the situation is addressed appropriately?