$$f = \sqrt{ \frac{c-v}{c+v} }$$
for (This is the relativistic Doppler shift)
$$E = \gamma mc^2$$ $$ \Rightarrow E = \frac{ mc^2 }{ \sqrt{1- \frac{ v^2 }{ c^2 } } }$$
The energy conservation is respected if you use the relativistic Doppler effect.
Basically the energy measured depends on the reference frame where you are.
The same applies to photons emitted by the cosmic background.
Consider that at $z=1000$ then the velocity of the emitted light is near the speed of light.
Then a $3000K$ black body would appear to have a $3K$ wavelength today... simply because the wavelength and hence the energy is measured in our rest frame.
To put it in a simpler form:
$$E= f h$$
$$f_s = \gamma f_o$$
(where $f_s$ is the frequency of the source and $f_o$ is the frequency of the observer)
$$ \Rightarrow E_o = \frac{hf_s}{\gamma}$$
Where
$$\gamma = \frac{1}{ \sqrt{ 1 - \frac{v^2}{c^2} } }$$
To put it in wavelength, simply use:
$$c = f \lambda$$ (where lambda is the wavelength)
So the energy seems smaller for the observer at rest than for the moving observer.
It is simply a relativistic effect.
Nothing is created or lost.