--> f = ((c-v)/(c+v))^1/2 fo (This is the relativistic Doppler shift)
E = gamma * mc^2 -> E = mc^2/(1-v^2/c^2)^1/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:
fs = gamma*fo (Doppler)
(where fs is frequency of the source, and fo is frequency of the observer)
-> Eo = h * fs/gamma
Where gamma = 1/(1-v^2/c^2)^1/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.