Can I call additional conditions on potentials a Gauge choice? Let's say I have an electromagnetics problem in a spatially varying medium.  After I impose Maxwell's equations, the Lorenz gauge choice, boundary conditions, and the Sommerfeld radiation condition, I still have more unknowns than equations and the solution for (say) the magnetic vector potential is not uniquely determined by the above.  This does actually happen when you formulate the equations in plane-stratified media in the plane-wave / Fourier domain.  The way to proceed that I have seen is to choose that one of the cartesian components of the vector potential is zero, i.e. impose one of the following as an additional condition to ensure uniqueness of the potentials: $A_x=0$, $A_y=0$ or $A_z=0$.  We could of course make up an infinite number of other conditions that leave the fields invariant.
My question is, can I call the above arbitrary choice about the vector potential a "gauge choice"?  The reason for imposing it seems to be identical to the reasons we normally impose the Lorenz or Coulomb gauge, namely that the field equations don't dictate anything about certain potential quantities, the choice makes solving the equations uniquely possible, and the physical $\mathbf{E},\mathbf{H}$ fields are invariant to the extra condition on the potentials.
 A: Setting $A_z = 0$ is usually called 'axial gauge'.  (The choice of the $z$-direction is arbitrary, of course.)  This is a perfectly valid gauge condition, and used a lot in QCD.
However, I don't think it makes sense in general to simultaneously impose Lorenz gauge and axial gauge.  This is too many constraints; you'll kill off physical degrees of freedom.  However, in specific situations, it may be that your boundary conditions are actually imposing these constraints, so accidentally imposing them a second time with the gauge condition causes no harm.  It's hard to say more without knowing exactly what you're doing.
Is it possible that you are missing the secondary constraint implied by the gauge choice?
A: Per your comment to user1504, you are correct: the Lorenz gauge contains considerable arbitrariness.  
To wit, suppose potentials $\Phi, \boldsymbol{A}$ satisfy:
$$ \nabla^2 \Phi - \frac{1}{c^2} \frac{\partial^2 \Phi}{\partial t^2} = - 4 \pi \rho $$
$$ \nabla^2 \boldsymbol{A} - \frac{1}{c^2} \frac{\partial^2 \boldsymbol{A}}{\partial t^2} = - \frac{4 \pi}{c} \boldsymbol{J} $$ 
$$ \boldsymbol{\nabla \cdot A} + \frac{1}{c} \frac{\partial \Phi}{\partial t} = 0  \quad  \text{ (Lorenz condition)}$$
Then, if $ \Lambda $ is a scalar that satisfies the wave equation:
$$ \nabla^2 \Lambda - \frac{1}{c^2} \frac{\partial ^2 \Lambda}{\partial t^2} = 0 $$
the restricted gauge transformation (restricted because of the condition on $\Lambda$):
$$ \boldsymbol{A} \rightarrow \boldsymbol{A} + \boldsymbol{\nabla} \Lambda \quad, \quad \Phi \rightarrow \Phi - \frac{1}{c} \frac{\partial \Lambda}{\partial t}$$
preserves the Lorenz condition.
Caveat! This analysis applies in vacuum.  Extension to a homogeneous, isotropic medium looks straightforward, but for a spatially varying background like you posit, I don't know...
A: You can only make the gauge choice $A_z=0$ if for any given potential you can set it 0 as the result of a Gauge transformation, a transformation which doesn't change the Lagrangian (or rather the action - or Maxwell's equations in your question, which are the equations of motion of some Lagrangian). This is, yes, a more complicated way of saying we can change the potentials as long as the fields don't change. The symmetries of the Lagrangian form a Lie group, which for EM is U(1). The addition of the divergence of a scalar adds a boundary term to the action which vanishes for physical potentials.
For electromagnetism, it ends up that by adding scalar divergences we can kill off two degrees of freedom and be left with two (I'm not really sure how to prove this from knowing the Lie group, if someone could expand here that would be great). These are transverse in the radiation gauge, but we can kill them off any way we like. In matter, I'm pretty sure you can't just kill off the longitudinal DOF. There will still be only two DOF but a different mix of $\Phi,A_x,A_y$ and $A_z$, i.e. two constraints on the 4 DOF.
