We show, that the 2D XY-model with random phase shifts exhibits for low temperature and small disorder a phase with quasi-long-range order, and that the transition to the disordered phase is {it not} reentrant. These results are obtained by heuristic arguments, an analytical renormalization group calculation, and a numerical Migdal-Kadanoff renormalization group treatment. Previous predictions of reentrance are found to fail due to an overestimation of the vortex pair density as a consequence of independent dipole approximations. At positions, where vortex pairs are energetically favored by disorder, their statistics becomes effectively fermionic. The results may have implications for a large number of related models.