The existence of dark matter particles that carry phenomenologically relevant self-interaction cross sections mediated by light dark sector states is considered to be severely constrained through a combination of experimental and observational data. The conclusion is based on the assumption of specific dark matter production mechanisms such as thermal freeze-out together with an extrapolation of a standard cosmological history beyond the epoch of primordial nucleosynthesis. In this work, we drop these assumptions and examine the scenario from the perspective of the current firm knowledge we have: results from direct and indirect dark matter searches and cosmological and astrophysical observations, without additional assumptions on dark matter genesis or the thermal state of the very early universe. We show that even in the minimal set-up, where dark matter particles self-interact via a kinetically mixed vector mediator, a significant amount of parameter space remains allowed. Interestingly, however, these parameter regions imply a meta-stable, light mediator, which in turn calls for modified search strategies.