Speed of gravity Consider two objects presented in the figure below. Objects have equal masses and are separated by a distance of 60 light seconds. 
Assume that we move left object by 3 light seconds to the left in 30 seconds. This requires energy input, lets say it's equal to X. Change in potential energy is also equal to X.
Now, the right object does not 'know' yet that the left object was moved. Left object was moved 30 seconds ago and this information requires 60 seconds to reach the right object. 
We have 2 options: A: We can move the right object by 3 light seconds to the right with the speed of 0.1c now. 
B: We can move it with the same speed and by the same distance later - let's say after 60 seconds.
Clearly case A requires the same energy input as when moving left object = X. This is because right object still 'thinks' that the left mass in the same place.
In the case B the right object 'knows' that the left mass was move so we will need less energy to move it. Energy needed < X.
The end state in A and B is the same. Why it is possible to achieve it with 2 different energy inputs? If we choose method A the increase in potential energy is smaller than energy input X. Where is the missing energy?
Maybe the 'speed of gravity' is infinite?

A: "The end state in A and B is the same."  This is the fallacy.  The total state has to include the potential field of the gravitational field.  If you do things via A, the potential field disturbance has not yet propagated to the right-most body, so the potential energy field has not yet settled down.
After a few more seconds, the disturbance will reach the right-most body, and by staying in the same place, it will give up energy (to whatever hand is holding it there so it will stay there so that eventually you will reproduce the situation after method B.)  
In summary, you cannot really say the situation is the same until you wait for the potential field to "settle down" and be the same in both situations.
A: In order to calculate what happens in this situation, you need to work out appropriately how the gravitation field changes.  This requires the use of General Relativity.  Worse, General Relativity requires the local conservation of energy and momentum densities, which (unfortunately) seem not to be conserved in your proposed thought experiment.  This does not mean that there are not thought experiments that can be proposed.  But, this is all pretty hard (General Relativity is quite hard) and would imply lots of gravitational waves and similar.  And, energy would be conserved only if you took account of the gravitational waves that go to infinity. 
Actually, binary pulsars (look these up e.g on wikipedia) show these kinds of effects, and confirm General Relativity and the existence of gravity waves.  And, people have thought about situations in which the high-speed motions of gravitating bodies are important, but those are quite difficult.  One type of situation you could look at (if you want) is black hole coalescence, in which black holes move quite quickly, generate lots of gravitational waves and show what can happen when gravitating objects move quickly.  Both situations, but particularly the latter are quite difficult to treat.
