La ventaja es la semántica. Un menú es una lista de enlaces, con lo que lo lógico es usar una lista para crearlos. Los divs se usan para marcar zonas, puedes usarlos para englobar el menu si quieres, pero no para el menú en si. Es decir:
<div id="menu_lateral">
<ul>
<li><a href="#">Enlace 1</a></li>
<li><a href="#">Enlace 2</a></li>
<li><a href="#">Enlace 3</a></li>
<li><a href="#">Enlace 4</a></li>
<li><a href="#">Enlace 5</a></li>
</ul>
</div>
Respecto a los problemas de incompatibilidad la mayoría de los navegadores no tienen problemas con menús con listas. Y además la tendencia es que estos navegadores tiendan a desaparecer:
http://gs.statcounter.com/#browser_v...-200911-201011