Hace algún tiempo me desapareció el menú de Nuevo -> Documento de Texto. No sé como sucedió, pero la solución la he obtenido de: http://capitalhead.com/articles/new-text-document-option-missing-in-windows-xp-and-vista.aspx
Tenemos que descargar este archivo: notepad.zip
Dentro se encuentra un archivo .reg que debemos ejecutar para modificar el Registro de Windows. Una vez ejecutado, deberemos reiniciar el ordenador o simplemente reiniciar la sesión de nuestro usuario.
Actualización: el usuario Zeibe comenta que ha probado este método en Windows 8 y también funciona.