Are Maxwell's equations "physical"?
Just a quick complaint about naming first: Maxwell's equations are written in terms of the electric and magnetic fields, which are physical degrees of freedom. You're instead talking about the Euler-Lagrange equations of the Maxwell Lagrangian.
At the classical level, if we want to write electromagnetism in terms of a four-potential, that potential has to have a gauge symmetry to avoid redundancy. If you don't have a gauge symmetry, the theory simply won't be classical electromagnetism. Instead, waves with a fixed wavevector will have three independent polarizations.
However, such a theory has a deep problem: the equation of motion $\partial_\mu F^{\mu\nu} = 0$ only suffices to determine the evolution of the fields, not the potentials. That is, the classical theory is not deterministic! This directly corresponds to a loss of unitarity at the quantum level. Both these features are sufficiently bad that some would say gauge symmetry is a requirement for the theory to make sense.
Note that this isn't true if you add a mass term $m^2 A_\mu A^\mu$ to the Lagrangian; in this case the equation of motion is simply the Klein-Gordan equation for each component. This is the Proca theory, which makes perfect sense without gauge symmetry. However, the problems are reintroduced when the mass goes to zero. As such, gauge symmetry for the massless theory isn't really a choice, and it's not specific to quantization either; it's instead required at the classical level and transferred to the quantum.
You are correct that there are gauge degrees of freedom in the solution for $A_\mu$ - precisely the ordinary gauge transformations. But $A$ is not physical, the electromagnetic field strength $F$ is. There are no gauge degrees of freedom in $F$, and as an equation for $F$ Maxwell's equations are physical.
The polarization of the classical $A_\mu$ has nothing to do with any photons. There are no photons in a classical theory. Maxwell's equations alone classically fully suffice to allow only transverse EM waves, see e.g. this question and its answers.
The two answers above are respectable answers and reflect the present theory. I have a different answer, namely that th epotential is physical, and I have proven that it is the only correct one. 19 years ago I published a paper with a different formulation. It starts out with the Fermi Lagrangian ${\cal L}= \frac{1}{2} \epsilon_0 \partial_\mu A_\nu \partial^\mu A^\nu$, to arrive at the wave equation $\partial_\mu \partial^\mu A^\nu = \mu_0 j^\nu$. The potential $A^\nu$ is uniquely determined by the requirement of causality. Since the wave equation is bijective, current conservation, $\partial_\mu j^\mu = 0$ implies $\partial_\mu A^\mu = 0$ and vice versa. That is, only the transversal part of the solution space describes the field of conserved current. I show that the Lorentz force follows. The solution of the wave equation can be written in terms of a propagator, which is simply the Green's function of the d'Alembertian operator $\partial_mu \partial^\mu$.
Let me explain why I say that this formulation is the only correct one. In principle my formulation predict exactly the same measurement outcome as long as only electromagnetism is considered. The definitive argument however comes from gravitation. An electromagnetic energy-momentum distribution implies a gravitational field. In my theory the EM distribution is the Nöther distribution of the (Fermi) Lagrangian. This is not the case for the gauge invariant theory. The standard EM distribution of the Belinfante-Rosenfeld Lagrangian is an ad hoc modification of the Nöther form, and by this an ad hoc modification of the gravitational field. This ad hoc modification is necessary because the BR Lagrangian implies a non-gauge invariant, asymmetric (GRT requires symmetry) Nöther form.
There are many advantages to this formulation, as you can see for yourself in the paper.