Bien,
Ya comprendo un poco ese comportamiento raro.
http://www.w3.org/TR/css-text-decor-3/#line-decoration Cita: When specified on or propagated to a block container that establishes an inline formatting context, the decorations are propagated to an anonymous inline box that wraps all the in-flow inline-level children of the block container.
Es un poco complicado de explicar, pero a la ves es fácil de entender. Osea, el text-decoration se aplica a elementos en linea como a, span, "p", etc. Tu lo estas aplicando a un elemento de bloque por eso causa ese comportamiento raro.
Una ves que agregues los enlaces en el menu, ya no tendrás ese problema, pues los enlaces son elementos en linea y el text-decoration funcionara normal. Claro, siempre y cuando apliques el text-decoration a los enlaces y no los
li.
Saludos