Axion-mediated forces are enhanced by the presence of $CP$-violating axion couplings, which are however tightly constrained by electric dipole moment (EDM) searches. We discuss the underlying hypotheses behind different sources of $CP$ violation at high energies and the interplay between axion-mediated force experiments and EDM observables. Specifically, we identify various mechanisms, based on new sources of $CP$ violation or Peccei-Quinn symmetry breaking, that can significantly relax EDM constraints, leading to a substantial redefinition of the QCD axion window for axion-mediated forces. By considerably enlarging the QCD axion parameter space, our results provide a well-motivated target for experiments probing scalar axion couplings to matter fields. These include fifth-force tests of gravity, as well as searches for spin-dependent forces via precision magnetometry, proton storage rings and ultracold molecules.