Ti spiego perchè mi sento di escludere le intestazioni: semplicemente perchè le trovo esagerate per lo scopo. Io mi immagino sempre la struttura pulita, come dovesse essere letta da un lettore di schermo: una suddivisione così forte come con le intestazioni è forse ingiustificata.

I paragrafi li ammetterei nel caso in cui il menù sia ben marcato, ad esempio con un bel titolone prima e un'area ben definita:
codice:
<div id="navigazione">
   <h2>Naviga nel sito</h2>
   

Sezione 1:</p>
   <ul>[*]Link 1.1[*]Link 1.2[/list]
   

Sezione 2:</p>
   <ul>[*]Link 2.1[*]Link 2.2[/list]
</div>
Nel tuo caso mi sentirei di suggerire delle belle liste annidate.