Woah, didn't know that! I remember searching for older messages in Matrix be really bad. I only use IM software for 1to1 conversations, so I probably don't know the worst of the protocol.
Dendrite solves this by asking matrix.org for everyone else’s keys by default.
Sounds a bit too centralized for me