Predicting coupled ocean–atmosphere teleconnections is inherently difficult because oceanic thermal memory and atmospheric chaos impose markedly different limits on forecast skill. This study reconstructed and forecast the Atlantic Multidecadal Oscillation (AMO) and North Atlantic Oscillation (NAO) through the integrated, data-driven RIMEF framework using 912 monthly observations from January 1950 to December 2025. Sea-surface temperature data were obtained from ERSSTv6, whereas sea-level pressure and 500-hPa geopotential-height fields were derived from ERA5. AMO was reconstructed over 0–70°N using latitude-dependent cosine weighting and removal of the contemporaneous global-warming component. NAO was extracted through empirical orthogonal function analysis of pressure anomalies across 20°–80°N and 90°W–40°E. The predictor space comprised one- to six-month lags, rolling means, phase and trend components, and the AO, PDO, and NINO3.4 indices. RidgeCV, ElasticNetCV, Extra Trees, Random Forest, and HistGradientBoosting were evaluated at 1-, 3-, 6-, and 12-month horizons through leakage-free rolling-origin validation. ElasticNetCV produced the lowest one-month AMO error (RMSE=0/621), whereas RidgeCV performed best at three months (RMSE=0/772). For NAO, the optimal RMSE values were 1/032 and 1/059 at one and three months, respectively. Phase accuracy declined from 0/592 to 0/515, revealing rapidly deteriorating atmospheric predictability. What distinguishes this study is its integration of raw-field index reconstruction, multiscale feature engineering, temporally rigorous validation, SHAP-based explain ability, and uncertainty quantification within a unified architecture. The findings support regularized models for AMO and probabilistic, uncertainty-aware forecasting for NAO. Such a bifurcated strategy can improve climate services while preventing deterministic NAO forecasts from being interpreted beyond their empirically demonstrated predictability threshold practice.