Well, we know a lot about the crystal structures of several high-temperature superconducting compounds.  You could always make an educated guess of a new one based on these and then test it for the Meissner effect.