  The axion solution to the strong CP problem calls for an explanation as to
why the Lagrangian should be invariant under the global Peccei-Quinn symmetry,
U(1)_PQ, to such a high degree of accuracy. In this paper, we point out that
the U(1)_PQ can indeed survive as an accidental symmetry in the low-energy
effective theory, if the standard model gauge group is supplemented by a gauged
and discrete R symmetry, Z_N^R, forbidding all dangerous operators that
explicitly break the Peccei-Quinn symmetry. In contrast to similar approaches,
the requirement that the Z_N^R symmetry be anomaly-free forces us, in general,
to extend the supersymmetric standard model by new matter multiplets.
Surprisingly, we find a large landscape of viable scenarios that all
individually fulfill the current experimental constraints on the QCD vacuum
angle as well as on the axion decay constant. In particular, choosing the
number of additional multiplets appropriately, the order N of the Z_N^R
symmetry can take any integer value larger than 2. This has interesting
consequences with respect to possible solutions of the mu problem, collider
searches for vector-like quarks and axion dark matter.
