A well-known result in unconventional superconductivity is the fragility of nodal superconductors against nonmagnetic impurities. Despite this common wisdom, Bi$_2$Se$_3$-based topological superconductors have recently displayed unusual robustness against disorder. Here we provide a theoretical framework which naturally explains what protects Cooper pairs from strong scattering in complex superconductors. Our analysis is based on the concept of superconducting fitness and generalizes the famous Andersons theorem into superconductors having multiple internal degrees of freedom. For concreteness, we report on the extreme example of the Cu$_x$(PbSe)$_5$(Bi$_2$Se$_3$)$_6$ superconductor, where thermal conductivity measurements down to 50 mK not only give unambiguous evidence for the existence of nodes, but also reveal that the energy scale corresponding to the scattering rate is orders of magnitude larger than the superconducting energy gap. This provides a most spectacular case of the generalized Andersons theorem protecting a nodal superconductor.