Assessing the stability of a multiple testing procedure under dependence is important but very challenging. Even for multiple testing which among a set of Normal random variables have mean zero, which we refer to as the "Normal means problem", to date there lacks a classification of the type of dependence under which the strong law of large numbers (SLLN) holds for the numbers of rejections and false rejections. We introduce the concept of "principal correlation structure (PCS)" that characterizes the type of dependence for which such SLLN holds, and establish the law. Further, we show that PCS ensures the SLLN for the false discover proportion when there is always a positive proportion of zero Normal means. We also investigate the stability of two conditional multiple testing procedures for the Normal means problem, and show that the associated SLLN holds when in addition the decomposition of the covariance matrix of the Normal random variables that induces PCS is homogeneous in certain sense. Our results also provide a formal way to check if the "weak dependence" assumption, a widely used assumption in the multiple testing literature, holds for the Normal means problem. As by-products, we establish a universal bound on Hermite polynomials and a universal comparison result on the covariance of the indicator functions of the two p-values of testing the marginal means of a bivariate Normal random vector and the correlation between the two components of the vector. These are of their own interests.