Reduction of recombination losses in dye-sensitized solar cells (DSC) is vital to fabricate efficient devices. The electron recombination lifetime depends on the relative energetics of the semiconductor and the redox pair and on the chemical nature of the electrolyte (hole conductor). In this work, the behavior of the electron lifetime in DSC devices prepared with various solvents (acetonitrile, valeronitrile, ethylene carbonate, pure ionic liquids), additives (lithium ions, TBP), and redox pairs (iodide/iodine, Co(II)/Co(III)) is thoroughly studied using high-extinction dyes. Lifetimes were extracted by means of small-perturbation electrochemical techniques (impedance spectroscopy, intensity-modulated photovoltage spectroscopy) and open-circuit voltage decays. To ensure a safe inner comparison and a proper interpretation, all devices were constructed using the same type of TiO2 electrode and the same dyes (C101 and Z907 for iodide/iodine and cobalt-based electrolytes, respectively). Furthermore, small-perturbation techniques and voltage decay provided consistent results. The lifetime shows a clear change of behavior when iodide/iodine electrolytes in organic solvents are compared to iodide/iodine in ionic liquids and with cobalt electrolytes. In the first case, the lifetime–voltage semilogarithmic plot exhibits a curvature, whereas in the second case the behavior is purely exponential. This observation is consistent with previous theoretical predictions based on the multiple-trapping model and the Marcus–Gerischer theory, which predict an exponential law for large reorganization energies and a curvature for small ones. The obtained results show that solvents or ligands that interact strongly with the redox mediator originate larger reorganization energies and lead to devices with shorter lifetimes. This can be interpreted as an enhancement of extra routes for electron recombination as a consequence of a wider overlap in energies between donor and acceptor states for strongly interacting chemical environments.