Over-parameterized neural networks, i.e., models with excess capacity that can fit training data exactly, have demonstrated superior generalization performance compared to classical models with balanced capacity. Nevertheless, their deployment in safety-critical domains re- mains severely constrained by their susceptibility to, e.g., natural per- turbations and adversarial manipulations. Verification techniques can solve such problems, but the computational cost of these methods of- ten scales poorly, specifically when applied to large models. In this work, we demonstrate that over-parameterization can be exploited not merely to enhance generalization, but also to mitigate neuron instability, one of the parameters affecting the efficiency of verification. Our experimental findings suggest that over-parameterization may serve as a crucial mech- anism for reconciling the long-standing trade-off between generalization and verifiability of neural networks.