Hola!,
Yo Lo Habia Probado(Por Que Incluso Tenia Mi Pagina Asi) y Funciona, Seguro Que Pusiste El Llamado Al Archivo Desde El Cuerpo Del Documento¿?(<body>), Mira:
Codigo menu.js:
document.write('<A HREF="http://www.com/">Enlace 1 </A>');
Codigo pagina.htm:
<html>
<head>
<head>
<body>
<script language="JavaScript" src="menu.js"></script>
</body>
</html>
Y Me Funciono Perfecto.
<CENTER><IMG SRC="http://www.galeon.com/jlmnetwork/FWPD.jpg"><BR><FONT COLOR=Black SIZE=2><I>"No Hay Cosas Imposibles, Solo Hombres Incapaces"</I></FONT></CENTER>