No podés colocar un tag script dentro de otro tag script de manera directa. También es necesario abrir el documento con document.open. Adicionalmente, conviene diferir la carga del archivo javascript con el atributo defer, para evitar problemas en explorer. Probá así:
Código PHP:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title></title>
<script>
function prueba(titulo){
var ventana = window.open('','','left=0,top=0,width=200,height=200,toolbar=no,location=no,status=no,menubar=no,resizable=no,scrollbars=no');
ventana.document.open();
ventana.document.write('<html><head><title>'+titulo+'</title>');
ventana.document.write('<scr'+'ipt defer="defer" src="test.js"></scr'+'ipt>');
ventana.document.write('</head><body>');
ventana.document.write('<span>holaaaaaaaaa</span></body></html>');
ventana.document.close();
}
</script>
</head>
<body>
<a href="javascript:prueba('Titulo de la ventana')">CLICK AQUI</a>
</body>
</html>