bueno, si pudieras utilizar server side includes sería muy fácil, pero tendrías que renombrar tus páginas shtml y tu servidor tendría que soportarlo también. en su defecto te recomiendo que en todas las páginas utilices un iframe y ahi coloques tu menú para lo que podrías utilizar un código más o menos así:
Código HTML:
<iframe src="paginaconmenu.htm" name="menu" width="100" height="400" marginwidth="0" marginheight="0" frameborder="0"></iframe>
obvio que si usaras server side includes sería todo mucho más fácil y alcanzaría con poner:
Código PHP:
<!--#include file="paginaconmenu.htm"-->
espero que eso solucione tu problema