Miller indices. What determines the appropriate axis?
There is no "appropriate" translation. You must remember that everything includes translational symmetry, including the Miller planes.

The Wikipedia page on crystal structures and Miller indices go into much more detail, but some key points:


The unit cells possess translational symmetry, so there are a set of Miller planes that also differ by translational symmetry.
The Miller indices (hkl) (which yes should be expressed in smallest possible integers) define the normal of the Miller plane.



  That is, (hkℓ) simply indicates a normal to the planes in the basis of the primitive reciprocal lattice vectors. Because the coordinates are integers, this normal is itself always a reciprocal lattice vector. The requirement of lowest terms means that it is the shortest reciprocal lattice vector in the given direction.


So in your case, you have to remember if you "move the origin", you have to also consider the symmetrically identical unit cells around the one in your picture. As I said above, there are an infinite set of identical Miller planes that simply differ by the translational symmetry of the lattice.