I'll just address a few points:
If phase is not shifted current and voltage are both at 1, 0.5 and 0 at the same time. So I expect the average power to be 0.5 voltage X 0.5 current. Without having done the math.
You are asking about sinusoidal waveforms so we have to be careful. The average of a sinusoid is zero so it is not much use in power calculations.
Instead, we use the True RMS (root mean squared) voltage and current measurement. This gives a measure of the equivelant DC voltage or current that would deliver the same power into a resistive load. For sinusoidal AC, \$ V_{RMS} = \frac 1 {\sqrt 2} V_{peak} \$ or about 0.701 × Vpeak.
There's a useful demo over at Wolfram Cloud. You can play with this to examine the effect of changing phase-angle.
Figure 1. Voltage (blue behind the orange current curve) and current in-phase. Note the green waveform is the shape of a sine2 and has twice the frequency of the voltage and current waveforms and is always positive.
However, if current and voltage are phase shifted the the values are like this: Voltage = 1 then Current = 0 Voltage = 0.5 then Current = 0.5 Voltage = 0 then Current = 1
In that case I expect the power to be lower than 0.5 voltage X 0.5 current.
As pointed out in other answers you have forgotten the sign of the voltages and currents and the resultant sign of the power. It will alternate between positive and negative.
Figure 2. Voltage and current 90° out of phase. Notice that for the first 90° the power is positive, then negative, then positive and negative again for one voltage cycle. The average power is zero!
Is the difference between the power without phase shift and the power with phase shift the reactive power? And if yes, where does this power go to. Because power can't be lost, it must be somewhere, right?
Think of it as energy storage. A capacitor is, in some ways, like a rechargeable battery. It takes power to charge it up but (ignoring chemical and heating losses for simplicity) the energy is stored and can be recovered later.
In the case of the capacitor the energy is stored in the electric field between the capacitor plates. In the case of the inductor the energy is stored in the magnetic field.
Figure 3. At 45° phase shift we can see that the power curve is positive most of the time but dips negative for some of the time. This would be the case in a partially inductive load. Those little dips into the negative are where the inductor is giving back what it stole on the positive portion of the power curve.
Now what's the problem with all of this?
The problem is that a consumer with a poor power-factor will have energy sloshing in and out of their utility connection, causing current to flow, causing voltage drop along the line as a result and all with no benefit to anyone. Most likely it will cause poor voltage regulation for themselves and their neighbours. A costly solution is for the utility company to install much heavier cables to handle the additional current without voltage drop. The sensible solution is to apply power-factor correction in the consumer's building so that the energy just sloshes back and forth internally but not on the utility supply.