Align low-res images of a moving feet
Very interesting problem
I will focus on the second aspect of your question, how to improve it.
What I would do next, based on the experience you shared is to combine the two methods.
One problem of your first approach is that it accumulates the errors in the alignment between multiple images. A possible approach would be to use your focus measure to align the images iteratively.
$$ F_{i} = F_{i-1} + translate(image_{i}, o_{i}) $$
$$ o_i = \arg\min_{o}\quad  focus\left[ F_{i} + translate\left(image_{i}, o\right) \right]$$
This approach is maybe not the best at the beginning, but after the first step it have the advantage of not accumulating errors in the same way as if you compute $o_i$ as using only $image_i$ and $image_{i-1}$. Notice that $F_{i-1}$ aggregates all the previously aligned images, so if the one image is not aligned very well it will make so much difference since it sees how it was aligned before.
This is maybe not going to be as good as your global method. What I would try, to improve your global method is to make the displacement continuous with some type of interpolation, because a continuous optimization problem is much easier to solve than a discrete optimization problem, because can use the gradient information[1]. I am sure you are not doing the search for all the offsets independently that would be $s^N$, where $s$ is the number of possibilities in your search list.
Also instead of limiting the the displacements to a given range I think you could simply add some cost to the differences of the displacements $k \sum ||o_i - o_{i-1}||^2$, this makes sure that if have a high relative displacement between two frames the cost function will indicate that this is unreasonable.