Reduced density matrix functional theory (RDMFT) and coupled cluster theory restricted to paired double excitations (pCCD) are emerging as efficient methodologies for accounting for the so-called non-dynamic electronic correlation effects. Up to now, molecular calculations have been performed with real-valued orbitals. However, before extending the applicability of these methodologies to extended systems, where Bloch states are employed, the subtleties of working with complex-valued orbitals and the consequences of imposing time-reversal symmetry must be carefully addressed. In this work, we describe the theoretical and practical implications of adopting time-reversal symmetry in RDMFT and pCCD when allowing for complex-valued orbital coefficients. The theoretical considerations primarily affect the optimization algorithms, while the practical implications raise fundamental questions about the stability of solutions. Specifically, we find that complex solutions lower the energy when non-dynamic electronic correlation effects are pronounced. We present numerical examples to illustrate and discuss these instabilities and possible problems introduced by N-representability violations.