EDIT: There is an error in how the expanding universe model is treated in this post, which I have attempted to correct in post 173. I did not attempt to correct the issue here as this post has been up to long for that to be an effective correction.
i have never heard of this contradiction/paradox before. do you have a source for this? correct me if i'm wrong but i think you made it up.
first of all, red shift can be caused without space expanding. (i.e a tail light of a car moving away can also emit red shift). so it is not the expansion of space that produce the red shift, it is the side effect of it, which is objects moving further apart.
second, light doesn't travel from one point to another instantly. so before it reaches its destination, the space of the untraveled distant expands and automatically increases its travel time. this occurs independently from what happened during the the distant light had already traveled, the distant in which it might or might not have "sped up" to accommodate the expansion.
There is a velocity related Doppler effect that can be observed for near by galaxies that shifts both red and blue.
However, the cosmological redshift has for a very long time been explained as being caused by an expanding universe. Once light is emmited the velocity of its source cannot contribute to any additional or additive Doppler effect as it does for nearby galaxies.
How would a photon know that space itself is expanding? And how does the wavelength of light get stretched by the expansion of space? If the speed of light remains constant and the expansion of space essentially increases distances, the wavelength would not change the light would just take longer to travel the increased distance.
Even if space expands near c when comparing distance objects locally to the emission of light it can be considered just as flat as it is locally to earth.
I mentioned that you could talk this into a number of paradox discussions. You can run the math in a number of different ways, depending upon where you begin.
Few question a local curvature of space, length contraction and time dilation, when talking about gravity. There are equally few who see the global ramifications of curvatures in the reverse scales.
Close in to a gravity well time dilation and length contraction, due to GR effects results in light taking longer to move shorter distances.., or what from an external FoR appears shorter due to the curvature of space, time slows to a near stand still as you approach the event horizon of a BH....
How is it so difficult to apply the reverse to the great voids between gravity wells, where as the gravitational forces fade the curvature of space and time dilation run to the opposite extremes? It is hard to see because few ever explore it closely.
And to some extent you are correct! These are to a significant degree my own musings. Still it is generally consistent with GR.
Or as another option you could attribute some real physical character to space itself, which as it expands affects the wavelength of light directly, but that begins to sound like an ether model... Or once again there are any of several tired light models....
The truth is any of these three models could be at play we really have no direct way to tell one from another at this time.