We advance all optical spin noise spectroscopy (SNS) in semiconductors to detection bandwidths of several hundred gigahertz by employing a sophisticated scheme of pulse trains from ultrafast laser oscillators as an optical probe. The ultrafast SNS technique avoids the need for optical pumping and enables nearly perturbation free measurements of extremely short spin dephasing times. We apply the technique to highly-n-doped bulk GaAs where magnetic field dependent measurements show unexpected large g-factor fluctuations. Calculations suggest that such large g-factor fluctuations do not necessarily result from extrinsic sample variations but are intrinsically present in every doped semiconductor due to the stochastic nature of the dopant distribution. © 2013 American Physical Society.