Continuous-time random-walk Monte Carlo simulations of H-2 formation on a variety of grain surfaces of varying roughness based on olivine and amorphous carbon have been performed. With these inhomogeneous surfaces, we find that the temperature range over which efficient H-2 formation occurs in the interstellar medium is larger than it is for flat surfaces characterized by single values of the energy parameters for hydrogen-atom adsorbates. Our results show, in particular, that the formation of H-2 on non-flat interstellar grains can occur efficiently at typical surface temperatures in diffuse interstellar clouds, although the results are dependent on the strength of lateral bonds between H atoms and the surface.