Allora, la mia ricerca per una soluzione continua.
Il selettore universale per il margin e padding suggerito sopra, non sembra funzionare.

Ho confermato il mio dubbio riguardo il bug di explorer. Pare che se non specifico l'altezza del[*], explorer reagisce aggiungendo le spaziature verticali (guardatevi l'esempio che ho allegato sopra).

Il problema è che se specifico questa altezza, diciamo in 20px, correggo il problema su explorer ma ne provoco un altro su firefox: nel caso che la lunghezza del testo nel bottone supera la prima riga, disponendosi su due righe o più, i 20 pixel non bastano più e il testo fuoriesce dal bottone.
Insomma, il problema è che non posso usare height:auto; con explorer o specificare l'altezza con firefox.
A meno che non faccio un menu con voci non più lunghe di una riga. Purtroppo non è il mio caso.

Aiutoooo !