totalmente de acuerdo con webosiris.
Solo tenes que agregarle padding-right a los dos estados.
Código:
.mi-menu ul li a{
text-align:right;
background-image:url(../img/imagen1.gif);
background-repeat:no-repeat;
background-position:right;
padding-right:20px;
}
.mi-menu ul li a:hover{
text-align:right;
background-image:url(../img/imagen2.gif);
background-repeat:no-repeat;
background-position:right;
padding-right:20px;
}
Por otro lado, lo mejor para lograr el evento onover es usar un solo archivo de imagen con las imagenes de los dos estados y hacer el efecto cambiando la posicion de esa imagen. De esa forma evitarias el problema del retardo el efecto hasta que se cargue la segunda imagen.