Solutions of the Strong CP Problem based on the spontaneous breaking of CP must feature a non-generic structure and simultaneously explain a coincidence between a priori unrelated CP-even and CP-odd mass scales. We show that these properties can emerge from gauge invariance and a CP-conserving, but otherwise generic, physics at the Planck scale. In our scenarios no fundamental scalar is introduced beyond the Standard Model Higgs doublet, and CP is broken at naturally small scales by a confining non-abelian dynamics. This approach is remarkably predictive: robustness against uncontrollable UV corrections to the QCD topological angle requires one or more families of vector-like quarks below a few $10$s of TeV, hence potentially accessible at colliders. Because CP violation is communicated to the SM at these super-soft scales, our solution of the Strong CP Problem is not spoiled by the presence of heavy new states motivated by other puzzles in physics beyond the Standard Model. In addition, these models generically predict a dark sector that may lead to interesting cosmological signatures.