It depends on the meaning of physical theories. E.g., classical electrodynamics and classical Newtonian are examples of physical theories that are not completely background independent. Of course, both these examples are believed to be effective theories with a limited range of validity. For example, classical electrodynamics is not a valid approximation for the photo-electric effect or quantum entanglement in optics.
So maybe the question should be whether a fundamental physical theory (such that effective theories could, in principle, be derived from it) needs to be background-independent.
First of all, there is no logical necessity for a fundamental physical theory to be background-independent. We can easily imagine fundamental physical laws for a hypothetical world with hypothetical inhabitants, which are not background invariant.
So, the question remains whether a fundamental theory describing the physical world we live in must be background-independent. Ultimately, this depends on what the fundamental physical laws of our world are (which are yet unknown).
Our knowledge of the fundamental laws of physics is, of course, tied to empirical experience. So, we can ask whether the yet-known (non-fundamental) theories indicate that true laws of nature are background-independent. On one hand, we have General Relativity, which is empirically successful and shares a version of background independence. On the other hand, empirically successful quantum theories do not share this feature. Some physicists believe that the feature of background independence in general relativity is essential in the way that a successful theory succeeding general relativity most likely still has to feature background independence.
If a fundamental theory does depend on a background, the background should not affect dynamics in a way that contradicts empirically verified predictions of General Relativity. But in principle, it is possible that deviations of background independent theories are beyond empirical access (which, of course, is a fuzzy boundary).
Another question is: what is the precise meaning of background independence? In the context of general relativity, it means that the structure which is fixed a priori is just a manifold $M$ with its smooth structure, whereas other geometric structures like a Lorentzian metric $g \in \Gamma(T*M \otimes T*M)$ are determined by the initial conditions and the laws of the theory. On the converse, special relativistic theories usually are formulated starting with fixed Lorentzan manifold $(M,g)$, e.g. Minkowski space.
Note, however, that there is, of course, still the background structure of $M$. Smooth manifolds encode a lot of mathematical structures, including the topology and the notion of smoothness (which is not in general determined by topological manifolds). So, the meaning of background independence depends on what kind of structure you count to the background. For example, does a theory with a fixed topology of the bare manifold $M$ count as background-independent or not?
