Recent research suggests the widespread existence of the signal-to-noise paradox in seasonal-to-decadal climate predictions. The essence of the paradox is that the signal-to-noise ratio in models can be unrealistically small and models may make better predictions of the observations than they predict themselves. The paradox highlights a potentially serious issue with model predictions as previous studies may underestimate the limit of predictability. The focus of this paper is two-fold: the first objective is to re-examine decadal predictability from the lens of the signal-to-noise paradox in the context of CMIP5 models. We demonstrate that decadal predictability is generally underestimated in CMIP5 models possibly due to the existence of the signal-to-noise paradox. Models underestimate decadal predictability in regions where it is likely for the paradox to exist, especially over the Tropical Atlantic Ocean and Tropical Indian Ocean and eddy-rich regions, including the Gulf Stream, Kuroshio Current, and Southern Ocean. The second objective follows from the results of the first, attempting to determine if this underestimate of decadal predictability is, at least partially, due to missing ocean mesoscale processes and features in CMIP5 models. A suite of coupled model experiments is performed with eddying and eddy-parameterized ocean component. Compared with eddy-parameterized models, the paradox is less likely to exist in eddying models, particularly over eddy-rich regions. These also happen to be regions where increased decadal predictability is identified. We hypothesize that this enhanced predictability is due to the enhanced vertical connectivity in the ocean. The presence of mesoscale ocean features and associated vertical connectivity significantly influence decadal variability, predictability, and the signal-to-noise paradox.