European lawmakers have ruled that users on different platforms should be able to exchange messages with each other. Yet messaging interoperability opens up a Pandora's box of security and privacy challenges. While championed not just as an anti-trust measure but as a means of providing a better experience for the end user, interoperability runs the risk of making the user experience worse if poorly executed. There are two fundamental questions: how to enable the actual message exchange, and how to handle the numerous residual challenges arising from encrypted messages passing from one service provider to another -- including but certainly not limited to content moderation, user authentication, key management, and metadata sharing between providers. In this work, we identify specific open questions and challenges around interoperable communication in end-to-end encrypted messaging, and present high-level suggestions for tackling these challenges.