Long story short: work and change in kinetic energy are frame-dependent quantities, although the work-energy theorem holds in both frames. Using the fact that mass and force are frame-independent quantities, we can see that the extra change in kinetic energy as seen in the non-moving frame is due to the fact that an observer in this frame observes the force exerted as acting through a larger distance than that observed in the moving frame. In order to resolve the mystery of "where is the extra energy", we note that the total change in energy observed in the non-moving frame has two components, and the "missing" energy comes from the work that the one of the object needs to do in order to maintain a constant speed.
Here are the details:
Let's consider the following situation. A physics student is standing on a cart moving at a constant speed $v$. Let's call this reference frame $A$. She throws a ball forward, exerting a force $F$ over some distance, and the final speed of the ball ends up being $v_{\textrm{A}}$ in this moving frame. Her lab partner is standing stationary on the ground (frame B) observing this process, and he sees the final speed of the ball to be $v_{\textrm{B}}=v+v_{\textrm{A}}$. Ignoring the factors of mass (because mass is a Galilean invariant), the change in kinetic energy observed in frame A is
$$
\Delta K_{\textrm{A}}=\frac{1}{2}v_{\textrm{A}}^2,
$$
and the change in kinetic energy observed in frame B is
$$
\Delta K_{\textrm{B}}=\frac{1}{2}(v+v_{\textrm{A}})^2-\frac{1}{2}v^2 = \frac{1}{2}v_{\textrm{A}}^2 + vv_{\textrm{A}}>\frac{1}{2}v_{\textrm{A}}^2 = \Delta K_{\textrm{A}}.
$$
Apparently, there is a larger change in kinetic energy in frame B as in frame A, as the OP observed!
To resolve this mystery, we need two things. First, it can be straight-forwardly proven that the force $F$ exerted on the ball is also a Galilean invariant, and so both observers see the same force exerted on the ball. However, since the first student is standing on the cart, she sees herself exerting a force on the ball through some distance $d$, and so the work done on the ball is
$$
W_{\textrm{A}} = Fd.
$$
In frame B, the distance through which the force is exerted includes the distance that the cart has traveled during this time, i.e.,
$$
W_{\textrm{B}} = F(d +v\Delta t),
$$
assuming that that the throw takes an amount of time $\Delta t$.
The work energy theorem holds in both of these frames, and we can see how the energy added to the ball as observed in frame B is larger than that observed in frame A! In fact, we can show that they are equal.
The amount of time taken to accelerate the ball from a speed of $0$ to a speed $v_{\textrm{A}}$ over a distance $d$ in frame A is given by (again, ignoring mass)
$$
\Delta t = \frac{\Delta v_{\textrm{A}}}{a} = \frac{v_{\textrm{A}}}{F},
$$
and so, plugging this into the expression for the work done in frame B, we get
$$
W_{\textrm{B}} = F(d +v\Delta t)= F\left(d +v\frac{v_{\textrm{A}}}{F}\right) = Fd + vv_{\textrm{A}}.
$$
We can see that the extra work done as observed in frame B is exactly the extra amount of energy gained as observed in frame A compared to frame B.
Now, there's still some intuitive stuff to work out. Sure, work and changes in kinetic energy are frame-dependent, but it still feels like the energy is lost in going from one frame to another. Where is the meaning of the extra energy as observed in one frame versus the other. In particular, the OP mentions energy used by batteries.
In frame A, imagine that a battery-powered machine is the one throwing the ball. It really only has to supply an energy equal to $v_{\textrm{A}}^2/2$ to accelerate the ball in the moving frame! So where is that extra energy as seen in frame B coming from? It's coming from the cart. The cart is given a backwards kick by the pitching machine, because the machine is pushing backward on the cart in order to push forward on the ball. Thus, the cart must be powered in order to remain at a constant speed during the throw. How much energy is require to remain at a constant speed?
For the sake of argument, let's pretend that the pitching machine has zero mass. Then the force exerted backward on the cart is equal to the force exerted forward on the ball, by Newton's 3rd Law. To remain at constant speed during the throw, the cart must counteract this force by exerting its own force backwards on the ground. Of course, the amount of work done during this process is $Fv\Delta t$, and we already showed that this is equal to the extra amount of energy that is missing.