You should be able to decrypt the messages if you still have the old device to verify the new connection, or if you saved the encryption key that's setup when you first login to the account.

Appreciate it's not as simple as logging in, because that's the point of separating the encryption key from login creds in the first place. Even if your accounts credentials are compromised, previous messages aren't, and any future messages from the unverified device are flagged as suspicious.

XMPP has some good options. I tried utilising mov.im servers, which claims to have E2EE.(using conversations app to connect) Its very user friendly and just works. Though, I'm not sure how the encryption works on there as I'd already got my users used to element, and saw no reason to move (IMO its still a better option than signal due to the self hosting capabilities, but depends on what level of solution you're after)