Ok... Bastante completo :)
Por partes...
- Lo de "ejecutarlo con permisos de administrador" implica marcar el programa para que siempre se ejecute como usuario administrador... Aunque parece haber mas opciones como te dice en el articulo que te enlazo abajo.
- Para ver lo que tienes a la escucha en cada puerto, debes usar el netstat con opciones (en este caso nos interesan los puertos tcp): netstat -anp tcp... Y mirar los puertos de las IPs de la izquierda que estan en "LISTEN" (a la escucha).
- ssh-keygen hace tiempo que requiere el uso del parametro -t para generar la clave... Puedes poner el tipo de encriptacion que deseas usar (rsa o dsa)... Es decir, a tu linea deberías incluirle un -t dsa (o -t rsa), dado que el protocolo 2 de ssh admite claves no rsa, ya no se toman esas "por defecto".
- El fichero de configuracion del daemon es sshd_config (y si, parece que la lista de ficheros es correcta).
En cualquier caso, parece que, efectivamente, debe haber algun problema con los permisos efectivos de algun ejecutable, dll o carpeta... buscando en google he encontrado ésto, que tiene buena pinta y quizás te ayude:
http://www.kgx.net.nz/2010/03/cygwin...and-windows-7/
Yo me bajaría los últimos cygwin+openssh y probaría lo que comentan en el articulo. Parece sencillo, limpio e inspirado. Lo probaria yo mismo pero ultimamente estoy bastante liado... Ya me cuesta reponder a veces por aqui (aunque generalmente lo hago por distraerme un rato cuando me estreso, y por ir pillando ritmo) ;)
Suerte... Ya contarás ;)