Relaxation phenomena far from thermal equilibrium feature a rich phenomenology, including the thermal relaxation asymmetry. The latter states that heating occurs faster than cooling in overdamped harmonic systems quantified in terms of excess free energy and entropy production. Upon isolating the relevant relaxational contribution to the entropy production, we here algebraically prove the asymmetry in thermal relaxation in phase space in the entire range from overdamped dynamics to underdamped dynamics. We show that for the same setup as for overdamped dynamics (i.e., motion in harmonic potentials, also known as Ornstein-Uhlenbeck dynamics), even in the more general case of phase-space relaxation, i.e., underdamped dynamics, far-from-equilibrium heating is faster than cooling. The coupling of positions and velocities emerging in this generalization further underscores, in a striking manner, the intricate dynamics of such thermal relaxation processes that do not pass through local equilibria. Investigating the overdamped limit, our generalized approach reveals, interestingly, that an excess free energy contribution from the velocity degrees of freedom does not trivially vanish in the overdamped limit, but is instead affected by the precise interpretation of temperature quenches in overdamped systems.