Secure messaging systems are essential for ensuring privacy and confidentiality in today's digital communication. Thanks to the widespread adoption of end-to-end encryption, messages are accessible only to intended users, and advancements in protocol resilience against secret compromise have enhanced messaging systems' protection guarantees. However, several open challenges remain. This thesis investigates three of these challenges---active attack detection, metadata protection during key retrieval, and real-world deniability---and presents cryptographic and system-level solutions to strengthen the security and privacy of modern secure messaging systems.s The first contribution of this thesis addresses active attack detection in messaging. We address scenarios where the network can delay and drop messages, and where adversaries can impersonate parties and inject forged messages. We propose out-of-band detection mechanisms that always detect active attacks, and in-band mechanisms that detect attacks as soon as an honest message goes through. Optimizing these schemes, we also explore how active attack detection can be practically achieved. The second contribution addresses challenges in distributing cryptographic keys that enable parties to establish secure messaging channels. Metadata protection is crucial to safeguard users' social graphs, and security issues arise from potentially malicious service providers distributing adversarially-controlled keys. To address these challenges, we introduce authenticated private information retrieval, a cryptographic primitive that ensures clients 1) do not reveal their social graph to the messaging service and 2) either retrieve the correct key or abort. We implement and evaluate all our schemes, assessing the practicality of multi-server authenticated private information retrieval with Keyd, a PGP key-directory server we develop. Finally, we analyze cryptographic deniability in secure messaging systems and its practical relevance from technical and legal perspectives. Although often presented as a key feature in protocols like Signal, our technical modeling, which incorporates real-world factors, along with legal analysis of 140 court cases in Switzerland, reveals that deniability typically fails in practice. Based on these findings, we discuss whether deniability is desirable and explore the challenges of designing systems that offer practical deniability. Together, these contributions advance the resilience, privacy and practical applicability of secure messaging systems in the face of real-world adversaries.