> There's no clear solution for it from an encryption perspective without a big tradeoffs (like requiring all participants to be online at the same time).

I wonder if that's why Telegram's secret chats do in fact require users to be online at the same time for key exchange. I've used it before and I had to wait a while for the other party to come online.