Okay, I found the answer. It's Newton's 3rd. One needs to take account of the work done on the system on which the reaction force acts and calculate the change in kinetic energy of the composite system while taking into account conservation of momentum.
In particular, the extra term $v_0 \int_{t_0}^{t_{1}} F dt $ in the expression for change of the kinetic energy of car A as seen by B' is proportional to the change of momentum of car A (i.e. $\int_{t_0}^{t_{1}} F dt $). When you calculate the change in kinetic energy of the road (generally attached to some massive planet) on which car A according to Newton's III acts with the force $(-F)$, and then add that to the total change of energy in each reference frame, we find a corresponding extra term in B equal to $-v_0 \int_{t_0}^{t_{1}} (-F) dt $. without going through the details I got the following answer. I have carried the signs through to make it more clear which parts came from where. (M is the mass of the planet/road and m is the mass of car A).
$$\Delta E=\int_{t_0}^{t_1}Fvdt+\int_{t_0}^{t_1}(-F)(-v_0-\frac{m}{M}v)dt $$
$$ \Delta E'=\int_{t_0}^{t_1}F(v_0+v)dt+\int_{t_0}^{t_1}(-F)(-\frac{m}{M}v)dt $$
So one obtains the same result on the fuel gauge in both B and B', which is satisfying. However, initially I was confused how $v_0$ could still appear in the expression. After all, this is merely the relative velocity of some external observer, right? Not so fast, it turned out.
What I didn't realize was the important point that there is a huge difference between the scenario above, and a seemingly similar example where car A is at rest relative to the road at $t=t_0$ in reference frame B (say B is now the person in the ditch). And B' is taken to be some car travelling in the opposite direction with constant velocity $-v_0$. The initial result is completely the same as above: car A accelerates from velocity $v(t_0)=0$ to $v(t_1)$ in reference frame B (the person) and from $v_0$ to $v(t_1)+v_0$ in B' (the other car), and thus the same results for $W_B$ and $W_B'$ as above are initially found. However, once the change in energy of the underlying planet enters the calculations, things play out very differently: you get a $v_0 \int_{t_0}^{t_{1}} (-F) dt $ term in $W_{B'}$ cancelling the existing $v_0 \int_{t_0}^{t_{1}} F dt $ in that expression, while not much happens with $W_B$.
$$\Delta E=\int_{t_0}^{t_1}Fvdt+\int_{t_0}^{t_1}(-F)(-\frac{m}{M}v)dt $$
$$ \Delta E'=\int_{t_0}^{t_1}F(v_0+v)dt+\int_{t_0}^{t_1}(-F)(v_0-\frac{m}{M}v)dt $$
So the total work done is luckily the same in each reference frame in both scenarios, but the actual amount of energy differs by an amount $v_0 \int_{t_0}^{t_{1}} F dt $. What somehow seem to matter is whether $v_0$ is merely the velocity of some observer in the background, or the initial velocity of the thing being pushed against relative to the "pusher".
If this is true the moral is that it really must require more energy for the same amount of time to push on something which has a negative component of velocity towards you compared to pushing with the same force against something that is at rest or has a positive component of velocity towards you! wow. That was actually not what I expected the answer to be. I hope I didn't make a sign error somewhere.