Is the Axiom of Choice critical for the mathematical basis of any physical theory?

It is not. The physical laws are always formulated as an algorithmic computation for producing an answer to what happens in a physical setup with a finite computation, if perhaps you need more computating to get better accuracy. The computations in ZF and ZFC are the same, the computational aspects are absolute, and you could use Peano Arithmetic for formulating physics, except you might not have as elegant a formulation, since you would have to represent real numbers in finite approximation. It is further true that if you start with ZF, no choice, and just look at Godel's minimal model containing the ordinals, L, then choice holds in the model. This means that whatever model you want to use for set theory, there is a submodel obeying choice. So you won't prove anything wrong by assuming choice. But the reason choice is wrong is because it contradicts probabilistic intuition in ways that are unnecessary and stifling. So in physics, you are better off denying choice, and assuming every subset of R is Lebesgue measurable. This makes defining certain path-integrals, like those for a free field, or for Brownian motion, or for supersymmetric theories with an explicit Nicolai map, a piece of cake. In physics mathematics, you don't bother with worrying that probability is inconsistent with choice, and you allow theorems whose proof involves random picks, something which is not possible in the presence of choice. In fact, using random picks, it is easy to see that every subset of R is measurable (this is the formal definition of saying random-picks make sense), that R does not have a basis as a vector space over Q, and that there are equivalence classes of real numbers that do not admit a choice function. It is always better to have probability than axiom of choice, so one will not get progress in measure theory without rejecting choice.

I'm not a physicist, so take this with a grain of salt. What do you mean by "prove?"  We start from some physical laws (empirically observed to be true), and use mathematics to find consequences.  If we used the axiom of choice at some point along the way, you might object that the result used AC and shouldn't be trusted.  If the result turned out to be empirically false, though, you can't tell whether it was AC that lead you astray, if your initial physical laws actually weren't quite right, or if you aren't modeling your problem mathematically in the correct way. For the most part, the AC is concerned with things that are very very infinite, much more infinite than things that will come up in the real world.  Most of mathematics that is needed for science works just fine without the AC.  The AC is in no way needed for differentiation, integration, or just about anything that the typical scientist uses.

I think that the theoretical foundations for quantum mechanics rely on the fact that every Hilbert space has an orthonormal basis, which can only be proven with the Axiom of Choice.