I prefer to look at it based on certain Laws and observations.
- The First and second Law of Thermodynamics are true
Energy is conserved and the universe is moving towards increasing entropy.
The Hubble constant is accurate and the universe is expanding at an exponential rate given by $a(t) = e^{Ht}$, where the constant $H$ is the Hubble expansion rate and $t$ is time. As in all FLRW spaces, $a(t)$, the scale factor, describes the expansion of physical spatial distances.
Redshift is the displacement of spectral lines toward longer wavelengths (the red end of the spectrum) in radiation from distant galaxies and celestial objects. This is interpreted as a Doppler shift that is proportional to the velocity of recession and thus to distance.
Blueshift a shift toward shorter wavelengths of the spectral lines of a celestial object, caused by the motion of the object toward the observer.
You say -
Light coming from galaxies that are going away from us is redshifted. Since the energy of a photon is purely dependent on its frequency one may conclude that the energy of these photons decreases. The same light coming from the same star in the same galaxy will be seen to a planet in that galaxy as it "actually" is. So dependent on the relative motion the energy will be seen, differently. How does this not conflict with the conservation of energy?
Ok let's say that is true we are experiencing a redshift but at the same time let's consider another observer who is moving at the same speed as our recession speed but towards the photon emitter source he is experiencing a blueshift. Each photon will have redshift and a corresponding blueshift depending on the relative frame of refences{one moving towards and one moving away}. The following picture makes it clearer.
"Dopplerfrequenz" by Charly Whisky 18:20, 27 January 2007 (yyy) - Own work. Licensed under CC BY-SA 3.0 via Commons.

An animation illustrating how the Doppler effect causes a car engine or siren to sound higher in pitch when it is approaching than when it is receding. The pink circles represent sound waves.
The energy from each siren waves doesn't change but depending where you are you will here a higher or lower pitch.
Now on a cosmologic scale the with an exponentially expanding universe with local Hubble horizons and trying to decide if the universe is a closed or open system leads to a cluster of different methods to try and verify the Conservation of energy of the universe. But a good way to think about this is to imagine open local systems exchanging matter and energy with each other across the universe and the sum of their energy diferences will be zero
thereby conserving energy.