This paper develops exact solution methods for the maximum mortality rate clique problem, which aims to identify a cluster of diseases in a comorbidity graph associated with the highest mortality rate among patients whose healthcare encounters are recorded in electronic health records. We establish the NP-hardness of the problem and propose two mixed-integer linear programming formulations, a combinatorial branch-and-bound algorithm, and a logic-based Benders decomposition (LBBD) framework. A hybrid LBBD variant that strategically invokes the combinatorial algorithm to strengthen node relaxations offers a computationally effective approach. The framework accommodates side-constraints on the discovered cliques, such as age-based restrictions, revealing qualitatively distinct lethal disease combinations that are unlikely to be driven solely by elevated baseline mortality in elderly populations. This optimization framework offers a practical and flexible tool for medical researchers seeking to uncover lethal multimorbidities to study progression and potential interactions.