Robust quantum systems rely on having a protective environment with minimized relaxation channels. Super-conducting gaps play an important role in the design of such environments. The interaction of localized single spins with a conventional superconductor generally leads to intrinsically extremely narrow Yu-Shiba-Rusinov (YSR) resonances protected inside the superconducting gap. However, this may not apply to superconductors with more complex, energy-dependent order parameters. Exploiting the Fe-doped two-band superconductor NbSe2, we show that due to the nontrivial relation between its complex-valued and energy-dependent order parameters, YSR states are no longer restricted to be inside the gap. They can appear outside the gap (i.e., inside the coherence peaks), where they can also acquire a substantial intrinsic lifetime broadening. T-matrix scattering calculations show excellent agreement with the experimental data and relate the intrinsic YSR state broadening to the imaginary part of the host's order parameters. Our results suggest that nonthermal relaxation mechanisms contribute to the finite lifetime of the YSR states, even within the superconducting gap, making them less protected against residual interactions than previously assumed. YSR states may serve as valuable probes for nontrivial order parameters promoting a judicious selection of protective superconductors.