> and it still happens today (at least with elements.io) that a message or two can get lost when you restart your client in an unfortunate moment

Is that unlucky moment during Element sending/trying to send the message to the server?

In this case Element stores messages now until they are sent (since 1.7.26).

Otherwise, don't see how this could happen.