Consider a magnetic field, $\mathbf{B}(x,z)$ given by
$$\begin{aligned}
\mathbf{B}(x,z) &= [B_x(x,z),\ B_y(x,z),\ B_z(x,z)] \\
&= \left[-\frac{l}{k}\cos(kx),\ -\sqrt{1-\frac{l^2}{k^2}}\cos(kx),\ \sin(kx)\right]\exp(-lz),
\end{aligned}$$
where $l^2\le k^2$. Since $\mathbf{\nabla\cdot B}=0$ we can write
$$\mathbf{B}=\mathbf{\nabla \times A},$$
for some vector potential $\mathbf{A}$. If we impose the Coulomb gauge condition (i.e. $\mathbf{\nabla\cdot A}=0$) then I believe this ensures that $\mathbf{A}$ is uniquely defined by the equation above.
I have calculated that $\mathbf{A}$ is given by
$$\begin{aligned}
\mathbf{A}(x,z) &= [A_x(x,z),\ A_y(x,z),\ A_z(x,z)]\\
&=\begin{cases}
&\left[-\frac{l}{k^2\sqrt{1-\frac{l^2}{k^2}}}\cos(kx),\ -\frac{1}{k}\cos(kx),\ \frac{1}{k\sqrt{1-\frac{l^2}{k^2}}}\sin(kx)\right]\exp(-lz), & l^2<k^2, \\
&\left[0,\ -\frac{1}{k}\cos(kx),\ 0\right]\exp(-lz) , & l^2=k^2.
\end{cases}
\end{aligned}$$
Consider the case where $l = \sqrt{1-\epsilon}\,k$, for $\epsilon \ll 1$. We see that small changes to $\epsilon$ lead to minor changes to $\mathbf{B}$ but can lead to infinitely large changes in $A_x$ and $A_z$. Have I made an error somewhere? Do you know if this has any physical consequences? According to this Wikipedia article, "The Coulomb gauge is a minimal gauge in the sense that the integral of $A^2$ over all space is minimal for this gauge". Therefore, we can conclude that for any gauge, infinite changes to the vector potential can occur from small changes to the magnetic field.
Best Answer
The Coulomb gauge as such does not fix $A$. You may still make the transformation $A\mapsto A+\nabla \psi$ provided $\nabla^2 \psi = 0$. Only if you ask for $\psi \to 0$ at infinity, then $\psi=0$ and the gauge is unique. However, as your field is unbounded (as $z\to -\infty$) there is no 'minimal gauge' in your case and the total energy is infinity. Also, the formula for an explicit construction by convolution does not work in the present case (integrals do not converge).
By a suitable gauge transformation (and staying in the Coulomb gauge) you may in fact locally get rid of the $\ell\to k$ blowup.
In the present case, you may e.g. take $\psi = \frac{1}{k^2 \sqrt{1-\ell^2/k^2}}\sin(\ell x)e^{-\ell z}$. Both $x$ and on $z$ are multiplied by the same constant $\ell$, so that $\nabla^2 \psi=0$. Then calculate $A\mapsto A+\nabla \psi$ and note that in a neighborhood of $x=0$ there is no longer a singularity as $\ell\to k$, because you get factors like $(\cos(\ell x)-\cos(k x))/\sqrt{1-\ell^2/k^2}$.
It is unbounded in the $x$ direction unlike your other solution. But as I said there is no contradiction with the statement in wiki as your field is unbounded.