  We study the simplest theories with exact spacetime parity that solve the
strong CP problem and successfully generate the cosmological baryon asymmetry
via decays of right-handed neutrinos. Lower bounds are derived for the masses
of the right-handed neutrinos and for the scale of spontaneous parity breaking,
$v_R$. For generic thermal leptogenesis, $v_R \gtrsim 10^{12}$ GeV, unless the
small observed neutrino masses arise from fine-tuning. We compute $v_R$ in
terms of the top quark mass, the QCD coupling, and the Higgs boson mass and
find this bound is consistent with current data at $1 \sigma$. Future precision
measurements of these parameters may provide support for the theory or, if
$v_R$ is determined to be below $10^{12}$ GeV, force modifications. However,
modified cosmologies do not easily allow reductions in $v_R$ -- no reduction is
possible if leptogenesis occurs in the collisions of domain walls formed at
parity breaking, and at most a factor 10 reduction is possible with non-thermal
leptogenesis. Standard Model parameters that yield low values for $v_R$ can
only be accommodated by having a high degree of degeneracy among the
right-handed neutrinos involved in leptogenesis. If future precision
measurements determine $v_R$ to be above $10^{12}$ GeV, it is likely that
higher-dimensional operators of the theory will yield a neutron electric dipole
moment accessible to ongoing experiments. This is especially true in a simple
UV completion of the neutrino sector, involving gauge singlet fermions, where
the bound from successful leptogenesis is strengthened to $v_R \gtrsim 10^{13}$
GeV.
