Why does a rocket engine have increasing power as the speed of the rocket increases? Sorry to repeat this question, but I got no definite answer last time, so I am trying to state the question more clearly. 
Power = force x distance / time = force x velocity.
So if we apply a small constant force, as velocity increases, we get power which keeps increasing with the velocity. How is it possible to obtain increasing power from a small constant force? 
Specifically, consider a rocket in space, which has a large supply of fuel, burns fuel at a small constant rate, meaning the input power is constant and the generated force (thrust) is also constant. As it accelerates from zero to millions of m/s, we are getting increasing power from the small constant force.  How is this possible? Where does the increasing power come from, when the power from the fuel was constant?
Our assumptions


*

*We do not approach the speed of light, so I am not seeking a relativistic solution. 

*I am not considering the reduction of mass of the rocket as it burns fuel. If we considered the reduced mass, then it would increase the obtained acceleration, velocity and power still further, from the small constant input power, so would not solve the problem.  

*Rocket theory states that thrust does not depend on the velocity of the rocket with respect to the observer, it only depends on the exhaust velocity relative to the rocket, so as the rocket accelerates (to beyond the exhaust velocity), the thrust really will be constant, by burning a small constant amount of fuel. 


Previous attempts at solution
The answer which came closest to solving the problem was that when the rocket is at rest, we are accelerating both the rocket and exhaust in opposite directions, so we are spending the energy of the fuel on both, and only a small portion of the input power is used for accelerating the rocket, most of it is used for accelerating the exhaust. As the rocket speeds up, the velocity of the exhaust relative to the observer reduces, so we spend more of the input power in accelerating the rocket and less on accelerating the exhaust. However, this answer fails as the rocket exceeds the exhaust velocity, and both the rocket as well as the exhaust are moving forward relative to the observer. Now, as the rocket accelerates forward, the exhaust accelerates forward too, so the power for accelerating both keeps increasing again, so we get an increasing power from a small constant input power. How is this possible?
Also someone commented that we are not getting increasing power, but we have to provide increasing power to keep accelerating under a small constant force. How does this help to solve the problem in our scenario? We are still burning fuel at a small constant rate and the rocket keeps accelerating. Where does the extra power that we need to “provide” come from? Why does the rocket keep accelerating although the equation clearly states that it cannot do so unless we provide increasing input power (increasing fuel)?
 A: The increased power comes from the fact that the fuel is moving along with the rocket. 
That is, suppose the exhaust velocity is $w$ and the current speed of the rocket is $v$. When the rocket is at rest, burning a small mass $m$ of fuel releases energy $mw^2/2$. When the rocket is moving extremely fast, so $v \gg w$, the amount of kinetic energy this fuel would have before burning is $mv^2/2$, which is much bigger than the energy released by burning it! So the increased power output comes from harvesting the existing kinetic energy of the fuel itself.
Of course, this kinetic energy didn't come from nowhere. It was put there by the burning of earlier fuel, so everything checks out and you don't get energy for free.
A: Your argument about the exhaust is correct and it does not fail. Even if both, the exhaust and the rocket move in the same direction relative to you, the force on the exhaust is in the opposite direction that the motion of the exhaust. Thus, being negative, the effect of the force is to descelerate the exhaust.
Imagine that instead of fuel you have a lot of springs attached to the rocket's wall, that push little pebbles out of the rocket. The force of the spring on both the rocket and the pebble remains the same regardless of the rocket speed, and so the total power of the released (previously stored) potential energy, but the power on the rocket increases positively with speed and the negative power on the pebbles become more and more  negative.
NOTES
1) Both, work and power are not invariants, they depend on the refernce frame
2) In a reference frame in which the rocket is moving, the power on the pebbles is negative, they start with the rocket's speed and end up with a slower speed. Power is not a vector, is a scalar, but becomes negative if force and displacement have opposite directions.
3) The pebbles do transfer energy to the rocket as they slow down
$EK_i^{pebble}+EK_i^{rocket}+EP^{spring}=EK_f^{pebble}+EK_f^{rocket}$
A: 
However, this answer fails as the rocket exceeds the exhaust velocity, and both the rocket as well as the exhaust are moving forward relative to the observer. Now, as the rocket accelerates forward, the exhaust accelerates forward too, so the power for accelerating both keeps increasing again.

The exhaust does not accelerate forward.  The exhaust may move forward (relative to the observer), but it does not accelerate forward.
Consider the case where the rocket is already observed to be moving forward faster than the exhaust speed.  The mass that will become the exhaust is moving at $v_e + x$, where both $v_e$ and $x$ are positive.  After the reaction, the exhaust mass is moving forward at $x$.  Instead of accelerating forward it has decelerated.  The velocity is now less, and the kinetic energy of the mass has decreased.  This change in KE must be balanced by an increase of energy elsewhere.  In this case it allows for the KE of the rocket to increase.
A: I think that the problems stems from the definition of "power" you are using. As it is defined, it doesn't seem to indicate the actual energy per unit time that the burning of the fuel delivers. Instead, I will try to compute the energy that the fuel REALLY has to input into the rocket, and we will see that everything checks out. To do that, I will place myself in a "stationary" frame of reference and compute the difference in KE in $t$ and $t+dt$ to compute the instantaneous power.
Velocities aligned with the rocket will be positive (read : velocity of the rocket is aligned with z-axis).
At time $t$, the rockets velocity is $v$, its mass is $M+m$.
At time $t+dt$, the rockets velocity is $v+dv$, its mass is $M+m-dm$ and some fuel has been expelled at velocity $-u$ with respect to the rocket. So, the fuel has velocity $-u+v$ with respect to the stationary frame (this is true to first order, we could have chosen $-u+v+dv$ and still gotten the same result to first order).
Writing conservation of momentum between $t$ and $t+dt$ :
$$dp = (M+m-dm)(v+dv)+(v-u)dm - (M+m)v = (M+m)dv-udm +O(dm\times dv) = 0$$
Thus $\frac{dv}{dt} = \frac{u \phi}{M+m}$ where $\phi = \frac{dm}{dt}$. We indeed obtain a constant acceleration provided the effective burnt fuel is negligible ($m = cst$) and the flux of matter is constant $\frac{dm}{dt}$.
Now, let's see the energy gain of the system between $t$ and $t+dt$. This is the energy that must be provided by the burning of the fuel. We will be using the equation $dv = \frac{udm}{(M+m)}$ that we derived earlier. Again we keep only first order as $dv$ and $dm$ are infinitesimal.
$$dK = \frac{1}{2}(M+m-dm)(v^2+2dv)+\frac{1}{2}dm(v-u)^2-\frac{1}{2}(M+m)v^2 = (M+m)dv-vudm+\frac{1}{2}dm u^2 = \frac{1}{2}dm u^2$$
Where the last equation follows from the conservation of momentum. If we "divide" by $dt$, we finally get that 
$$\frac{dK}{dt} = P_{inst} = \frac{1}{2}\phi u^2$$
So it seems that there is no problem at all. Indeed, the instantaneous power provided by the fuel is always the same. The energy that is injected into the rocket seems to be always constant as expected.
Now onto the question. The power that you use is the following definition :
$P = \frac{F\cdot d}{t}$. As far as I understand, here $d$ is the total distance on which the force has acted on the rocket. However, you write $\frac{d}{t} = v$ where v is the instantaneous velocity. As I undertand it, $\frac{d}{t} = v_{mean}$ is the mean velocity so it is a totally different quantity.
Another thing to point out is that, although the acceleration of the rocket is constant, the force acting on it seems not to be. Indeed, using Newton's Second law:
$$dp_{rocket} = (M+m-dm)(v+dv)-(M+m)v = -vdm +(M+m)dv= -vdm +udm = (u-v)dm$$
So, dividing by dt : $F_{rocket} = (u-v)\phi$. The actual force acting on the rocket seems to decrease as the rockets accelerates. This seems a little counter-intuitive, but it is understandable : when you push out some fuel, two effects happen : you lose some momentum because you lost some mass, you gain some momentum because the fuel "pushed you". Those two effects balance in such a way that the acceleration is constant and proportional to $u\phi$. 
However, the actual Force acting on the rocket is not constant, and apparently becomes a "dragging" force when the rocket speed is higher than $u$. This is because the lost momentum from the released mass is much bigger than the gained momentum from the push, at high velocities of the rocket.
Having realised that the force isn't actually constant, I start to see why would the definition $P = F\cdot v$ lead to some unexpected results. Also, I am not sure how right this definition is if you start by $P = F\cdot d/t$. Indeed, as far as I understand, here d is the total distance traveled, so we don't have $d/t = v$ as the rocket is accelerating. However, I still have trouble understanding the validity of this definition in general, so I may be wrong. 
Let me know if this answer is satisfying or not. 
A: You are correct that a constant force $F$ applied to an object of mass $m$ will generate an increasing amount of power as the object accelerates. This extra power doesn't "come from" anywhere physical; rather, it comes from the way that kinetic energy is defined. Specifically, what makes it possible is the fact that kinetic energy grows faster than velocity with increasing velocity. 
An object's kinetic energy $K$ is defined:
$$K=\frac{1}{2}mv^2$$
Power is the rate of work being done. The work-energy theorem says that the amount of work done on an object is equal to the object's change in kinetic energy, so the power imbued to the rocket is just the rate of change of $K$. Plugging in $v=\frac{F}{m}t$ (from the classic $F=ma$) for an object accelerating from rest, we have that
$$K = \frac{1}{2}\frac{F^2}{m}t^2$$
so, differentiating,
$$P = \frac{dK}{dt} = \frac{F^2}{m}t$$
meaning that power increases over time.
