Vale, según yo veo en IE se desplaza al poner el cursor sobre la lista. Una solucion rápida al problema es no utilizar las medidas del padding de #menu en porcentaje, si lo usas en pixeles el problema desaparece, lo que me gustaría saber es porqué IE hace esto, supongo que el ser un navegador pésimo le hace liarse con las medidas en porcentaje 1ª
.
De todas formas no consigo encontrar la explicación exacta ya que el fallo está provocado de alguna forma por la propiedad background, si la sustituyes por ejemplo por un text-decoration no sucede nada raro al igual que si le aplicas el background al hover del <li> en lugar de al del <a>, pero esto último solo funciona en Mozilla 2ª
Por otro lado veo que asignas display:block a los enlaces para asi poder darles un width, esto en Mozilla funciona perfectamente pero explorer a mi me ha pasado que al asignarles height sigue basandose en el tamaño de la fuente para dar el alto, ha sido una suposicion, pero al comprobarlo he visto que nada tiene que ver con tu fallo pero es interesante comentarlo ya que es otra cosa de las muchisimas a tener en cuenta para optimizar una web para este navegador.
Son posibles soluciones pero a pesar de ello no sabría explicarte porqué 3ª
Espero haberte ayudado. Un saludo.