The big bang was what scientists call "very hot". So hot that the atoms were in a plasma (the "fourth state of matter") for the first 370,000 years. Towards the end of that time, the whole universe had cooled to the same temperature as the surface of the sun. That's your mental picture - surface of the sun but everywhere. White hot and glowy.

As it cooled a bit more the plasma "condensed" into gas as we're familiar with (the "third state of matter"). This is much like water vapour (third state) condensing to become water (second state).

Gas is transparent (you can see through the atmosphere) instead of glowy, so the photons that had been trapped (outrageous simplification) in the plasma were released. Fly, my pretties.

That's from about 370,000 years after the big bang. Expansion of the universe has redshifted (cooled) those photons by a factor of 1,100 - from ~5,000K (visible light) to 2.7K (microwaves).

But, frankly, that's peanuts.

Between the 2nd and 20th minutes of the universe, hydrogen was fused to helium. This phase of the evolution of the universe is under appreciated.

Start with ~10^80 protons.

Over a period of about 20 mins, ~10^79 helium atoms were formed by fusion. Strewth.

Don't forget that those fusions produce neutrinos, and they don't have a transparency problem. Can't cage those beasts.

The "Cosmic Neutrino Background" has been redshifted by 10,000,000,000 times since then.

Neutrinos have an absolutely tiny mass. So small that the neutrinos that came from SN1987A arrived at the same time as the photons after racing each other for 100,000 years.

The CNB may be the only neutrinos in the universe which have slowed down so much that they are no longer relativistic. There is no currently conceivable way to detect them, but we know that they are still there.

So, there's your answer - photons could be redshifted by 10^10 (ten million times more than the CMB) and they'd still "exist" as a moving probability wave. If the wave happens to interact with matter, then there will be a collapse of the waveform, and an incredibly low energy photon would be detected.

Much more boring answer...

Photons emitted near a Black Hole's event horizon are redshifted as they ascend. In theory, they could be redshifted by any amount, only depending on how close they were to the event horizon when they started out.

The issue is not whether they still exist, but whether there is any practical way to detect them.