Holas xurxinho
Yo probé tu código y puse el float:right dentro del estilo de #menuhorizontal y no invirtió los enlaces, ni en IE ni en Firefox, y sí movió la capa hacia la derecha.
Ahora sí, el asunto del ancho de cada LI sí que se ve distinto en uno y otro navegador al darle el float:right: en IE se ven de un ancho similar al de witdh, mientras que en Firefox simplemente no toma en cuenta ese valor. Si les quitas el valor a width creo que podrías hacer que se igualaran un poco más.
Pero ese es otro cuento. Como te digo, prueba lo de poner el right en el estilo general:
Código HTML:
#menuhorizontal{
background-color: #333;
border:1px solid #333;
height: 34px;
float: right;
}