You may be confusing work by a force and the net work.
I will remind you that the net work is defined as the sum of all work, and equals the change in kinetic energy of the object.
$$W_{\rm net}\equiv \sum_i W_i = \Delta {\rm KE} = \dfrac1 2 mv_f^2-\dfrac1 2 mv_i^2\tag1$$
On the other hand, the work by a certain force $\vec F_i$ on the object over some path $C:\vec r (t)$ is defined as
$$W_{\mathrm{by}\vec F_i}\equiv \int_C \vec F\cdot d\vec r \tag 2$$
If we assume that the force is constant, then Eq. (2) simplifies to the following familiar equation:$$W_i = \vec F_i\cdot \Delta\vec r=F_i\Delta r\cos\theta$$
What is that work that was done at an interim path point - can we calculate it in principle?
Yes, by equation (2) you can calculate the work done by a force over a path.
How to make sense of what happens when the box is being pushed back to origin - why the work is negative?
The net work along a closed path (i.e. you start and end at the same point) is not necessarily zero.
If it's just you pushing the box (i.e. the force you apply = the net force), then in that case, the net work = the work you do = change in kinetic energy:
$$W_\mathrm{net} = W_\mathrm{by \; you}=\Delta \mathrm{KE}$$
If the box starts off with speed $v$, but when it's back at its initial position, it has a speed not equal to $v$, then the net work was not zero (since there is a change in kinetic energy, because the speed of the box is different at the start and end).
However, what you are probably referring to, is: the box starting from rest, moving, then finishing at the same spot at rest (i.e. starts from rest, moves, finishes at rest). In that case, what happens is you apply some your force to speed the block up and move it, hence giving it some speed. However, in order to slow the box down (so it finishes at rest), you must apply a force opposite to the path the block takes to slow it down. Forces acting against the object's path (i.e. slowing it down) result in negative work. Therefore, the same work you do to speed the box up, you will have to do that (negative) same amount of work to slow it down. So, the total work you do is zero.
After all it's still being pushed, so we're doing work. Is it because of arbitrary choice of coordinates?
Yes it's being pushed, and yes you're doing work. Assuming you provide the net force, if you do zero work it's either because (i) you never speed the object up, or (ii) because you speed the object up and then you slow it down such that it starts and finishes with the same speed.
Coordinate systems have nothing to do with it. You can do the math in spherical or cartesian or any type of coordinates, if the forces and path are the same, the work won't change.
I'd also recommend reading the following: Net Work Done When Lifting an Object at a constant speed. It should clear up your doubts.
