Is it strictly necessary to require gauge invariance of the action and equations of motion? When writing down an action for a gauge theory, we require that the action be gauge invariant. This is typically taken to mean that the action must be written explicitly in terms of gauge invariant quantities. My question is how we justify this requirement.
We know that the time evolution of physical observables must not depend on the choice of gauge. One might then guess that there should exist EOM that are formulated in terms of gauge invariant quantities, and hence conclude that the action (which is responsible for generating the EOM) should also be formulated in terms of gauge invariant quantities. But I see no reason why this must be the case.
For instance, it seems possible that one could have a theory for which there does not exist EOM that describe the theory purely in terms of gauge invariant quantities. Such a theory could still be gauge invariant in the sense that when one solves the equations in an arbitrary gauge, one obtains gauge-independent solutions for the observables. Here one is forced to use gauge dependent language to write down the fundamental equations of the theory, but the solutions turn out to be gauge invariant.
Is there some theorem that says that for any EOM that yield gauge invariant solutions, there exists a formulation of those EOM purely in terms of gauge invariant quantities?
Edit:
I should rephrase "EOM formed out of gauge invariant quantities" to "EOM that retain their  form when gauge transformed." This modified definition holds, for instance, for the Maxwell equations even though they can be formulated in terms of $A_\mu$.
I would also want to say the same thing about the action: i.e. replace "action formed out of gauge invariant quantities" with "action that retains its form when gauge transformed."
The modified question is thus: if one wishes to obtain theory with gauge invariant solutions, must the action and EOM "retain their form under a gauge transformation?" 
 A: Just as a starting-point, it might help clarity if we're a little more careful about what it would be for a solution to be "gauge-invariant". I'll use the example of electromagnetism to illustrate. So suppose that we have written Maxwell's equations in terms of potentials, and having done everything in terms of coordinates:
$$\partial_\mu\partial^\mu A^\nu - \partial_\mu\partial^\nu A^\mu = J^\nu$$
So a solution to Maxwell's equations, in these terms, is a function $A_\mu : \mathbb{R}^4 \to \mathbb{R}^4$ which satisfies the above equation (taking some function $J^\nu: \mathbb{R}^4 \to \mathbb{R}^4$ as given).
Now, such a solution is not itself a gauge-invariant object: if we act upon it by a gauge transformation
$$A_\mu \to A_\mu + \partial_\mu\lambda$$
we get a different function $A'_\mu = A_\mu + \partial_\mu \lambda$. However, this function is guaranteed to also be a solution to Maxwell's equations; it is in this sense that gauge transformations are symmetries of the Maxwell equations. So requiring solutions to be gauge-invariant in this sense is definitely not something we want!
But in your question, you ask about obtaining ``gauge-independent solutions for the observables" (my emphasis). So you might have in mind the following requirement: that for gauge-related $A_\mu$ and $A'_\mu$, the observables associated to $A_\mu$ are the same as those associated to $A'_\mu$. And that will indeed be the case, for the trivial reason that gauge-invariance is generally a necessary condition on considering some quantity to be an observable!
Bearing all this in mind, let's now consider your question. It's a little opaque to me what kind of EOMs you have in mind here. If you mean "can we have EOMs which are gauge-invariant, despite not being formed out of gauge-invariant terms?" then the answer is straightforwardly yes: just consider the Maxwell equations above (neither $\partial_\mu\partial^\mu A^\nu$ nor $\partial_\mu\partial^\nu A^\mu$ is gauge-invariant). In the more general case of a Yang-Mills equation, which asserts (roughly speaking) that an exterior-derivative-of-a-connection type thingy is equal to a current, neither the left- nor right-hand sides of the equation are themselves invariant; it's just that they transform in the same way, so that the equation as a whole is invariant.
Alternatively, you might mean "can we have EOMs which are gauge-invariant, despite it being impossible to write them down using only gauge-invariant terms?" To the best of my knowledge, that's an open question. It's certainly true that there are gauge-invariant theories for which no such formulation is known: as I say, general Yang-Mills equations aren't formulated purely in terms of gauge-invariant objects. (This question comes up in discussions of "loop representations" of gauge theories, where we want to try and specify the content of such a theory purely in terms of holonomies or Wilson loops. Although there are some theories, such as electromagnetism, for which an explicit formulation of the EOMs in terms of loops is known, for most theories no such explicit formulation is available.)
Finally, you might mean "could we have some EOMs which are not gauge-invariant, but which have gauge-invariant solutions?" Given that what we mean by a gauge transformation is typically (in part) that it is a symmetry of the equations under consideration, it's not clear that this question is well-formed. Or, if it is just being asked with respect to some particular kind of transformation (e.g. that of $A_\mu$ above), then the answer will either be trivially "no" if we take the first meaning of "gauge-invariant solution" I mentioned above, or trivially "yes" if we take the second meaning (assuming we continue to insist that observables be gauge-invariant - although if gauge transformations are not symmetries, the motivation for doing so largely drops away).
