The highest energy cosmic rays should interact with the cosmic microwave background radiation (CMBR) if the energy of the proton is about 6×10^19 eV (in the rest frame of the CMBR) into a Delta+ resonance. This is called GZK cutoff.

The average "lifetime" of a proton for flying without interaction at this energy is about 160 Megalightyears.

A Japanese experiment (AGASA) claimed to have found some of this very high energetic particles, which led to speculations, despite the big systematic uncertainties.

Auger (south, in Argentina) recently reported (maybe preliminary) to have found as well some, but
a) there is a reduction in the current on these very high energetic particles
b) they were able to track much of the particles origin (at this high energies the intergalactic magnetic fields don't bend the trajectory too much) back to known active galactic nuclei (AGN). AGNs are likely huge black holes (as we have likely a smaller one in our galactic center). On their accretion discs many light year long streams are accelareted to produce high energy particles of all types.

The surprise about their existence though shows only a lack of our understanding of the AGNs, not of the special relativity and not super heavy BigBang relicts, which would have been the most interesting for particle physics.
Of course this is not yet completely safe, as Auger is only shortly in operation and it might be that some have different origin, but I wouldn't bet against it.

Der Amerikaner ist die Orchidee unter den Menschen
Volker Pispers