I've gotten off the starting block with implementing the message update JEP. The implementation has matured in the 2 years (!) since I drafted the JEP and it's become a lot simpler.
What I've done so far: use gajim's sent message history to select a message, then insert the replace element when retransmitted. The replace element is all that we need to correct typos.
The image also illustrates the elegant degrading as neither client supports the protocol. Yet.
Gajim tx done. Gajim rx and Psi tx/rx to come. And a shiny new XEP