  We show that models in which the strong $CP$ problem is solved by introducing
an axion field with a mass enhanced by non-QCD UV dynamics at a scale
$\Lambda_{\rm SI}$ exhibit enhanced sensitivity to external sources of $CP$
violation. In the presence of higher-dimensional $CP$-odd sources at a scale
$\Lambda_{\rm CP}$, the same mechanisms that enhance the axion mass also modify
the axion potential, shifting the potential minimum by a factor
$\propto\Lambda^2_{\rm SI}/\Lambda^2_{\rm CP}$. This phenomenon of
$CP$-violation enhancement, which puts stringent constraints on the scale of
new physics, is explicitly demonstrated within a broad class of "small
instanton" models with $CP$-odd sources arising from the dimension-six Weinberg
gluonic and four-fermion operators. We find that for heavy axion masses
$\gtrsim 100$MeV, arising from new dynamics at $\Lambda_{\rm SI}\lesssim
10^{10}$GeV, $CP$ violation generated up to the Planck scale can be probed by
future electric dipole moment experiments.
