Hola,
mucho depende del efecto que quieres lograr pero de antemano el padding en elementos inline no funciona igual en todos los navegadores, bueno ok, sólo en IE.
Lo que hace la mayoría es mostrar los elementos
a como bloques y flotarlos.
En tu ejemplo, si no quieres modificar el background-color del vínculo al momento de hacer hover, entonces es mejor que el padding lo pases a los elementos
li. Todo depende de que tengas en mente para ese menú. Tienes publicada en internet esa página?
Saludos.