Hola cuasatar.
Yo lo plantearia con una función recursiva.
Código PHP:
function Menu($pId=0){
$sql="select * from menu where parentid=$pid";
$array=GetQuery($sql);
if(empty($array)){return "";}
foreach($array as $i=>$md){
$menu.="<li><a href=\"{$md[id]}\">{$md[nom]}</a></li>";
$menu.=Menu($md[id]);
}
$menu="<ul>$menu</ul>";
if($pId==0){$menu="<div>$menu</div>";}
return $menu;
}
No he testeado el código, pero la idea es esa, y te sirve para n niveles.
Cualquier duda, aquí estoy.
Saludos!