It was recently shown that domain walls from the spontaneous breaking of CP symmetry are exactly stable, and must be inflated away to recover a viable cosmology. We investigate the phenomenological implications of this result in Nelson-Barr solutions of the strong CP problem. Combined with the upper bound on the scale of spontaneous CP breaking necessary to suppress contributions from dangerous, nonrenormalizable operators to the theta angle, this puts an upper bound on the scale of inflation and the reheating temperature after inflation. Minimal Nelson-Barr models are therefore in tension with thermal leptogenesis, models of large-field inflation, or potential future observations of signals from topological remnants of an unrelated, subsequent phase transition. We study how extending Nelson-Barr models with a new, continuous chiral gauge symmetry can ameliorate this tension by forbidding the dangerous dimension-five operators. In particular, we show that gauging a linear combination of baryon number and hypercharge allows for an economic, anomaly-free extension of the minimal Nelson-Barr model, and discuss the phenomenological implications.