Remnants of AGN jets and their surrounding cocoons leave colossal magnetohydrodynamic (MHD) fossil structures storing total energies ~10^{60} erg. The original active galacic nucleus (AGN) may be dead but the fossil will retain its stable configuration resembling the reversed-field pinch (RFP) encountered in laboratory MHD experiments. In an RFP the longitudinal magnetic field changes direction at a critical distance from the axis, leading to magnetic re-connection there, and to slow decay of the large-scale RFP field. We show that this field decay induces large-scale electric fields which can accelerate cosmic rays with an E^{-2} power-law up to ultra-high energies with a cut-off depending on the fossil parameters. The cut-off is expected to be rigidity dependent, implying the observed composition would change from light to heavy close to the cut-off if one or two nearby AGN fossils dominate. Given that several percent of the universes volume may house such slowly decaying structures, these fossils may even re-energize ultra-high energy cosmic rays from distant/old sources, offsetting the ``GZK-losses due to interactions with photons of the cosmic microwave background radiation and giving evidence of otherwise undetectable fossils. In this case the composition would remain light to the highest energies if distant sources or fossils dominated, but otherwise would be mixed. It is hoped the new generation of cosmic ray experiments such as the Pierre Auger Observatory and ultra-high energy neutrino telescopes such as ANITA and lunar Cherenkov experiments will clarify this.