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.