Both cases kinda suck
Discussion
Hmm.. Myeah, but there is a different kind of key management involved. Deriving keys also means they're easier to vary and requires less need for persistence.
The issue is really on how to assemble the encrypted payload to let the receiver know which keys to use to decrypt without breaking the privacy or increasing the anonymity set.
Hmm.. that still leaves a lot of options open. E.g. is there prior info to work with? Would you be able to lookup "profile info" that gives a hint or provides some info, then you need less of an announcement message. I think you are aware that the basic encrypted DMs derive a single fixed key per pair of users.
I know it's not exactly what you asked for, but I played around with a small experiment which I hadn't had time to follow up on. Maybe it can give you some inspiration. (It didn't receive much attention at the time.)
I had explained it here:
https://lists.cypherpunks.ca/pipermail/otr-dev/2024-October/002574.html