Cells show remarkable resilience against genetic and environmental perturbations. However, its evolutionary origin remains obscure. In order to leverage methods of systems biology for examining cellular robustness, a computationally accessible way of quantification is needed. Here, we present an unbiased metric of structural robustness in genome-scale metabolic models based on concepts prevalent in reliability engineering and fault analysis. The probability of failure (PoF) is defined as the (weighted) portion of all possible combinations of loss-of-function mutations that disable network functionality. It can be exactly determined if all essential reactions, synthetic lethal pairs of reactions, synthetic lethal triplets of reactions etc. are known. In theory, these minimal cut sets (MCSs) can be calculated for any network, but for large models the problem remains computationally intractable. Herein, we demonstrate that even at the genome scale only the lowest-cardinality MCSs are required to efficiently approximate the PoF with reasonable accuracy. Building on an improved theoretical understanding, we analysed the robustness of 489 E. coli, Shigella, Salmonella, and fungal genome-scale metabolic models (GSMMs). In contrast to the popular "congruence theory", which explains the origin of genetic robustness as a byproduct of selection for environmental flexibility, we found no correlation between network robustness and the diversity of growth-supporting environments. On the contrary, our analysis indicates that amino acid synthesis rather than carbon metabolism dominates metabolic robustness.