Radial velocity (RV) searches for Earth-mass exoplanets in the habitable zone around Sun-like stars are limited by the effects of stellar variability on the host star. In particular, suppression of convective blueshift and brightness inhomogeneities due to photospheric faculae/plage and starspots are the dominant contribution to the variability of such stellar RVs. Gaussian process (GP) regression is a powerful tool for statistically modeling these quasi-periodic variations. We investigate the limits of this technique using 800 days of RVs from the solar telescope on the High Accuracy Radial velocity Planet Searcher for the Northern hemisphere (HARPS-N) spectrograph. These data provide a well-sampled time series of stellar RV variations. Into this data set, we inject Keplerian signals with periods between 100 and 500 days and amplitudes between 0.6 and 2.4 m s−1. We use GP regression to fit the resulting RVs and determine the statistical significance of recovered periods and amplitudes. We then generate synthetic RVs with the same covariance properties as the solar data to determine a lower bound on the observational baseline necessary to detect low-mass planets in Venus-like orbits around a Sun-like star. Our simulations show that discovering planets with a larger mass (~0.5 m s−1) using current-generation spectrographs and GP regression will require more than 12 yr of densely sampled RV observations. Furthermore, even with a perfect model of stellar variability, discovering a true exo-Venus (~0.1 m s−1) with current instruments would take over 15 yr. Therefore, next-generation spectrographs and better models of stellar variability are required for detection of such planets.