  The Minimal Supersymmetric Standard Model (MSSM) with conserved R-parity
suffers from several fine-tuning problems, e.g. the mu-problem and the problem
of proton decay through higher dimension operators. Both of these problems can
be avoided by replacing R-parity with a non-anomalous U(1)' gauge symmetry
which is broken at the TeV scale. The new gauge symmetry does not necessarily
forbid all renormalizable R-parity violating interactions among the MSSM
fields, and may allow for either lepton number or baryon number violation at
the renormalizable level. However, the proton decay problem resurfaces with the
introduction of new TeV-scale exotic fields which are required for gauge
anomaly cancellations. In this paper we investigate the issue of proton
stability in the presence of TeV-scale exotics. We show that there are large
classes of models in which TeV exotics do not destabilize the proton. We
classify the viable models according to the residual discrete symmetries after
U(1)' and electroweak symmetry breaking. In some of our examples the residual
U(1)' discrete gauge symmetry within the MSSM sector alone ensures that the
proton is absolutely stable, for any exotic representations. In other cases the
proton can be sufficiently long-lived, depending on the U(1)' and hypercharge
discrete charge assignments for the exotic fields. Our analysis outlines a
general scheme for ensuring proton stability in the presence of light exotics
with baryon and lepton number violating interactions.
