Metal hydrides with high thermodynamic stability are desirable for high-temperature applications, such as those that require high hydrogen release temperatures or low hydrogen overpressures. First-principles calculations have been used previously to identify complex transition metal hydrides (CTMHs) for high temperature use by screening materials with experimentally known structures. Here, we extend our previous screening of CTMHs with a library of 149 proposed materials based on known prototype structures and charge balancing rules. These proposed materials are typically related to known materials by cation substitution. Our semiautomated, high-throughput screening uses density functional theory (DFT) and grand canonical linear programming (GCLP) methods to compute thermodynamic properties and phase diagrams: 81 of the 149 materials are found to be thermodynamically stable. We identified seven proposed materials that release hydrogen at higher temperatures than the associated binary hydrides and at high temperature, T > 1000 K, for 1 bar H2 overpressure. Our results indicate that there are many novel CTMH compounds that are thermodynamically stable, and the computed thermodynamic data and phase diagrams should be useful for selecting materials and operating parameters for high temperature metal hydride applications.