Ciao.
Risposta breve:

display:block per i tag <a>, come giustamente ha indicato s1501.

Risposta esaustivamente particolareggiata:


  1. Il block su <a> estende l'elemento per tutta la larghezza disponibile (quindi per la larghezza di <li>), e questo è ok, ma il padding su <li> va a "rubare" dello spazio (che non sarà quindi sensibile al puntatore) sopra e sotto lo stesso <a>.

    Dovresti impostare il padding direttamente su <a>, non su <li>, in modo che <a> vada ad occupare l'intero spazio per tutta la larghezza e tutta l'altezza di <li>.

    (Vedo che questo punto lo hai già risolto da te)
     
  2. Il display:table applicato in quel modo non serve a molto, o meglio, ha una parvenza di funzionamento solo su CH, mentre su FF e IE9 non vedo una sostanziale funzionalità.

    Se intendi far funzionare gli elementi <li> come fossero celle di una tabella, sarebbe più opportuno applicare table-cell a questi.

    Inoltre...
     
  3. Tutta la formattazione del testo, sia quella che indichi su ".menu li" sia quella inserita nelle pseudo-classi :link e :visited, potresti applicarla direttamente a ".menu li a".
    In questo caso puoi fare a meno anche di specificare :link e :visited.
     
  4. Su IE9 non è supportato text-shadow.

    Se vuoi ottenere un effetto simile anche per IE9, e precedenti versioni, potresti aggiungere filter:shadow(...).

    Gli altri browser ignoreranno questa regola e manterranno comunque l'applicazione di text-shadow.
     
  5. Non è una regola fissa ma è buona norma mantenere una separazione, quanto più netta possibile, tra i contenuti HTML e la formattazione CSS.

    Se non è strettamente necessario è meglio non inserire codice CSS in-linea (vedi style="background-color:... ecc.). Sarebbe preferibile utilizzare invece delle classi e applicarne la formattazione sul CSS principale.

Chiaramente sono giusto dei consigli.

Posto una rivisitazione del tuo codice in base a quanto indicato:
codice:
<!DOCTYPE html>
<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
    <title>Senza nome 1</title>
    <style>
      .menu{
        position:fixed;
        top:0;
        left:0;
        border-bottom:4px solid #000;
        list-style:none;
        margin:0;
        padding:0;
        display:table;
        z-index:350;
        width:100%;
      }
      .menu li{
        display:table-cell;
      }
      .menu li a{
        display:block;
        color: #fff;
        font:bold small-caps 18px Arial,Helvetica,sans-serif;
        padding:10px 5px;
        text-align:center;
        text-decoration:none;
        text-shadow:1px 1px 2px #666;
        filter:shadow(color=#666666,direction=135,strength=2); /* IE8, IE9 */
      }
      
      /* Colori fondo voci menu */
      .menu .c1 { background:#404040 }
      .menu .c2 { background:#ffc900 }
      .menu .c3 { background:#ff8957 }
      .menu .c4 { background:#ff2525 }
      .menu .c5 { background:#bad700 }
      .menu .c6 { background:#49b6e8 }
      
      /* Voce attiva */
      .menu .active a { color:#e5e4e2 }
    </style>
  </head>
  <body>
    <ul class="menu">
      <li class="c1 active"><a href="#section1">Section1</a></li>
      <li class="c2"><a href="#section2">Section2</a></li>
      <li class="c3"><a href="#section3">Section3</a></li>
      <li class="c4"><a href="#section4">Section4</a></li>
      <li class="c5"><a href="#sectopm5">Section5</a></li>
      <li class="c6"><a href="#section6">Section6</a></li>
    </ul>
  </body>
</html>