>> If we have the ability to computationally determine these things without any experimental data needed, and we know we're looking for a specific band structure, wouldn't we just do an automated search of possible chemistries to find everything producing said band structure?

Isn't this a plot point in that one Star Trek movie (episode?) where they go back in time and program a current-day computer to do this?