If $A^\mu$ is not determined uniquely by Maxwell's equations, what happens if we solve for it numerically?

Not all initial value problems have unique solution. Your example of $\alpha$ function demonstrates that this initial value problem is of such kind.

In this case, the problem is in the system of partial differential equations

$$ \partial_\nu\partial^\nu A^{\mu}-\partial^{\mu}\partial_{\nu}A^{\nu}=0 $$ itself; it does not put enough constraint on the functions $\varphi(\mathbf x,t), \mathbf A(\mathbf x,t)$. It is somewhat similar to a situation in linear algebra that sometimes occurs where a system of $n$ linear equations for $n$ unknowns has infinity of solutions.

A slightly different way to see this: notice that nowhere in the above system of PDE can we find $\partial_t^2 A^0$ or $\partial_t A^0$ directly; only a spatial gradient of $\partial_t A^0$ is present. The equations for $A^i$'s do not relate them directly with time derivatives of $\varphi$.

This means that if we have a solution of the initial value problem $\varphi(x,t),\mathbf A(x,t)$ and replace the scalar potential by $\varphi' = \varphi(x,t)+ht^2$ at time $t = 0$ (where $h$ is a constant), the equations are still satisfied and at $t=0$, initial conditions are satisfied too. This would not be so obviously possible if the system contained directly time derivatives of $\varphi$. Consider a slightly different system

$$ \partial_\nu\partial^\nu A^{\mu}= 0, $$ (which in EM theory can be derived as a result of the Lorenz gauge choice) - this does constrain $\partial_t^2 \varphi$, so the above argument fails. I think this system should have a unique solution, because it is very similar to a set of equations for independent harmonic oscillators. However, for proof better check with mathematicians.

Are you asking for the physical or mathematical explanation? Dan Yand's answer gives the physical explanation.

Regarding the mathematical question: On what basis would you expect the field configuration to be uniquely determined by its initial data? Unlike for (uncoupled) ODE's, there's no theorem to that effect for general linear homogeneous second-order PDEs.