Abstract In Model-Based Diagnosis (MBD), the problem of computing a diagnosis in a strong-fault model (SFM) is computationally much harder than in a weak-fault model (WFM). For example, in propositional Horn models, computing the fifirst minimal diagnosis in a weak-fault model (WFM) is in P but is NP-hard for strong-fault models. As a result, SFM problems of practical signifificance have not been studied in great depth within the MBD community. In this paper we describe an algorithm that renders the problem of computing a diagnosis in several important SFM subclasses no harder than a similar computation in a WFM. We propose an approach for effificiently computing minimal diagnoses for these subclasses of SFM that extends existing conflflict-based algorithms like GDE (Sherlock) and CDA∗. Experiments on ISCAS85 combinational circuits show (1) inference speedups with CDA∗of up to a factor of 8, and (2) an average of 28% reduction in the average conflflict size, at the price of an extra low-polynomial-time consistency check for a candidate diagnosis.