La solución rápida a lo que preguntas es:
Código:
<div id="gratuit">
<a href="contactar/contactar.html">Contactar</a>
</div>
CSS
#gratuit { float:center; height:40px; margin-left:30px; width: 710px; }
#gratuit a {background:url(objetos/diagnostic.gif) no-repeat center center; display:block; }
#gratuit a:hover{background-image:url(objetos/diagnosticover.gif); }
Pero la solución más correcta, es como te han dicho antes. En vez de utilizar dos imagenes diferentes, utilizas una sola que contenga los dos estados y lo que cambias al hacer el hover, es la posición de la imagen. De esa forma, al cargarse los dos estados en la misma imagen, no hay un instante en que pueda no verse ninguna imagen, hasta que se carga la segunda.