[southerntofu]

> How should a "per user" verification work in your opinion?

The server could keep an append-only log of published keys, and then you could require m-of-n signatures of other published devices/keys to register a new one, in which case no further verification would be verifiable if you already trusted your peer's other keys. In addition, you could introduce peer keys in private rooms automatically and/or employ some form zero-knowledge proofs in public venues.

XEP-0450 Automated Trust Management is a first exploration in this direction. There a lot to explore and I only wished skilled cryptographers spent more time researching these issues on federated networks instead of advancing yet-another-centralized-messenger-of-the-month.

> Also you don't have to meet with everyone to verify new keys, you can just use a known good key for that.

Also known as a keyserver. But you could also employ cryptographic challenges like OTR does, like a shared password to establish the session.