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)