We study the thermodynamic stability at low temperatures of a series of alkali-metal-zinc double-cation borohydrides, including LiZn(BH4)(3), LiZn2(BH4)(5), NaZn(BH4)(3), NaZn2(BH4)(5), KZn(BH4)(3), and KZn2(BH4)(5). While LiZn2(BH4)(5), NaZn(BH4)(3), NaZn2(BH4)(5), and KZn(BH4)(3) were recently synthesized, LiZn(BH4)(3) and KZn2(BH4)(5) are hypothetical compounds. Using the minima-hopping method, we discover two new lowest-energy structures for NaZn(BH4)(3) and KZn2(BH4)(5) which belong to the C2/c and P2 space groups, respectively. These structures are predicted to be both thermodynamically stable and dynamically stable, implying that their existence may be possible. On the other hand, we predict that the lowest-energy P1 structure of LiZn(BH4)(3) is unstable, suggesting a possible reason elucidating why this compound has not been experimentally identified. In exploring the low-energy structures of these compounds, we find that their energetic ordering is sensitive to the inclusion of the van der Waals interactions. We also find that a proper treatment of these interactions, e.g., as given by a nonlocal density functional such as vdW-DF2, is necessary to address the stability of the low-energy structures of these compounds.