I think that the linked article described that messages that arrive out of order can still be decrypted despite the decryption keys being generated in a strict order. As far as I know, the order of the keys that are used to decrypt incoming messages also indicate the order in which the decrypted messages were sent.

So would a potential fix be just to add some metadata in the message somewhere that says when it was sent?

That would at least arrange the messages later on in the right order(I think they do this actually), but still means, they might get received in the wrong order. So you get the notification and look on your phone, but see only one of the later messages without context or knowing that there is missing information yet to arrive. That can be very irritating and annoying.

This is also annoying because you are seeing your messages on your end instantly, so your chat history order is not the same as everyone elses. This is most noticeable in a group with lots of messages.

Not a crypto issue, but a UI one though.

transcript consistency is usually something that matters in group chat, and signal/matrix/and pretty much all group chat apps rely on a trusted server to order messages.