En estos casos yo le doy un height de 1px al <li>, o al <a> si es el que tiene padding. Después le pongo el height en auto para los navegadores que aceptan child selectors (>). Ejemplo:
Código:
li {height:1px;}
html>body li {height:auto;}
Lo bueno de este tipo de código es que valida perfectamente.