We analyze the deviations from Maxwell-Boltzmann statistics found in recent experiments studying velocity distributions in two-dimensional granular gases driven into a non-equilibrium stationary state by a strong vertical vibration. We show that the ``stochastic thermostat'' model of heated inelastic hard spheres, contrary to what has been hitherto stated, is incompatible with the experimental data, although predicting a high velocity stretched exponential behavior with an exponent 3/2. The experimental observations validate the idea of effective restitution coefficients and allow us to refine a recently propounded random restitution coefficient model. Very good agreement is then found with experimental velocity distributions within this framework, which further provides sensitive probes to investigate the universality of the velocity statistics.