The existence of band structure of a crystalline solid comes from the Bloch theorem, which relies on the independent-electron approximation. Why do people still talk about the band structure for a strongly-correlated system, e.g. superconductors and topological insulators? In such strongly-correlated systems, shouldn't the independent-electron approximation become entirely invalid, rendering the band structure of a solid meaningless?
The most truthful answer, to my mind, to this is simply "because it often works in practice."
It is not obvious, a priori, that band structure should apply to any realistic solid. The Coulomb interaction is typically of the order of the Fermi energy. Nonetheless, thanks to the magic of Fermi liquid theory, this strong interaction somehow only results in renormalized Fermi quasiparticles. These quasiparticles only interact with each other weakly and yet have the same charge as the bare electrons, and therefore they can be reasonably expected to conform to band theory. Although debate is ongoing, there is some experimental evidence that this Fermi liquid behavior is even true in some cuprates.
Thus, justification of band theory is intimately related to justification of Fermi liquid theory. If you look around you can find plenty of arguments for when Fermi liquid theory is and isn't justified. But, again, they are all ultimately attempts after the fact to explain experimental results. I will quote Prof. Xiao-Gang Wen:
It is hopeless for a theorist to solve such as 'nasty' system [as interacting electrons in a solid], not to mention to guess that such a system behaves almost like a free electron system. Certainly, condensed matter physicists did not provide such a bold guess. It is nature itself who hints to us over and over again that metals behave just like a free electron system, despite the strong Coulomb interaction. Even now, I am amazed that so many metals can be described by Landau Fermi liquid theory, and puzzled by the difficulty to find a metal that cannot be described by Landau Fermi liquid theory.
(from the textbook Quantum Field Theory of Many-Body Systems)
Usually, when talking of the "band structure" of such a system one either refers to the non-interacting band structure (which relates to the free Green functions occuring in many methods to handle the interactions, like perturbation expansions or DMFT), or to the sharp features usually visible in the spectral function (which is more or less experimentally accessible via ARPES), these features reduce to $\delta$-like peaks at the bands in the non-interacting case. When considering, for example, simple thermodynamic properties the latter concept of "band structure" can be a reasonable approximation.
A side note: Nearly all the early research on topological insulators (especially when you refer by this term also to systems like Chern insulators and symmetry protected topological phases, the famous BHZ model, for example, is a non-interacting model) was on non-interacting systems. Symmetry protected topological phases do not require interacting electrons.
I think the notion of ‘band structure’ is deeply related to a “quasi-particle view” of an interacting system – even, an strongly interacting one. This means that although the original elementary excitations of the system (e.g., single electrons in a metal) do not provide a good and efficient description of the states and energies of the interacting system anymore, a properly ‘modified’ or ‘corrected’ version of them still would explain the behaviour of the system. This modification essentially comes from the interaction between the components of the system -- technically, called “renormalization”. Indeed, there is a priori no guarantee that this picture holds true, and in certain regimes, it does break down (e.g., formation of a superfluid out of interaction fermions for Helium-3). However, when the quasi-particle picture applies, as in the case of a “Fermi liquid”, then that implies that a good description of the interacting system can be made in terms of some “effective particles” which are weakly interacting with each other; at the lowest level of approximation (neglecting their weak interaction), these quasi-particles comprise a non-interacting system of quasi-particles for which a band-structure can be found. Indeed, the nature of such renormalized particles depends crucially on the interaction in the original system.