Luego de seguir buscando mas y mas, acabo de encontrar la solucion !!!
Voy a postearla con detalle la solucion porque a muchos que tengan servidores windows les va a servir para poder colocar prety Permalink.
Fuente donde encontre la solucion:
Pretty Wordpress Permalinks on IIS » tech.einaregilsson.com
(esta en ingles, asi que hare un resumen de la misma)
1) deben generar un archivo php con el siguiente codigo: (el archivo es para poder redirigir el error 404 a lo que ustedes realmente quiren... el permalink en el formato elegido)
<?php
$qs = $_SERVER['QUERY_STRING'];
$pos = strrpos($qs, '://');
$pos = strpos($qs, '/', $pos + 4);
$_SERVER['REQUEST_URI'] = substr($qs, $pos);
$_SERVER['PATH_INFO'] = $_SERVER['REQUEST_URI'];
include('index.php');
?>
2) una vez creado y guardado el archivo (le pueden dar el nombre que quieran, yo le puse redirect.php), lo copian por ftp a la carpeta donde tienen instalado el blog (al mismo nivel que el archivo index.php)
3) Copiado el archivo, entran al panel de control de su hosting windows, y deberian encontrar algun icono u opcion para "personalizar los errores" (en mi hosting, se llama "Páginas de Error Personalizadas" y tiene un iconito de un error 404) . Entran ahi y van a ver la lista de codigos de error, eligen el error 404 y en tipo de redireccion colocan /redirect.php (o el nombre que le hayan dado al archivo php).
4) Por ultimo en el panel de control del wordpress, ahora si van a ajustes, enlaces permanentes, escriben la estructura personalizada que quieren, ejemplo /%postname%/ . Guardan los cambios y veran que ya no tendran mas el error 404 y tambien han podido quitar el "index.php" de la url .
Espero que les sirva la solucionar y cualquier duda consulten que hace tiempo vengo investigando esta solucion.
Saludos.