Bei kleineren Seiten kann die ruhig fehlen (sieht ja dumm aus, wenn die Hälfte der Sitemap leer ist), und das Menü übersichtlich ist und alle Punkte auflistet. Ein gutes Menü ist immer besser als eine zusätzliche Sitemap (+höherer Plegeaufwand)! Denn dann ist das Menü quasi schon die Sitemap.
Bei größeren Seiten sollte eine Sitemap nicht fehlen. Habe auch gelesen, dass manche Leute viel lieber über eine Sitemap zu den gewünschten Seiten kommen, als über das Menü..