The critical node selection problem (CNP) seeks to determine the nodes to delete in a network to minimize the number of connected pairs in the resulting residual network. In several applications, the weights on the connections are either uncertain or hard to estimate so recently robust optimization approaches have been considered. In this presentation, we address very general uncertainty sets, only requiring a linear optimization oracle for the set of potential scenarios. In particular, we can deal with discrete scenario based uncertainty, Gamma-uncertainty, and ellipsoidal uncertainty. For this general class of robust CNP, we propose an exact solution method based on Benders decomposition and provide extensive computational results.