Re: "End-to-end encryption" isn't?
"Even then, though, you'd hope that 2 clients that had seen each other before would then warn their owners that the other ends key seemed to have changed."
This is a case of hanged if you do and hanged if you don't. If you use the same key all the time any messages which have been intercepted and stored in the past can be decrypted if the key is later compromised - which is more difficult if the server didn't store the key - but you can tell if the key's been changed. If you use a different key each time then past messages are safe but the key exchange is susceptible to MitM attack if the server is compromised.