Algunas respuestas:
1- El PR no tiene nada que ver con ser indexado. La unica relacion es que usualmente sitios con mayor importancia tienen mayor PR, y los sitios de mas importancia para el buscador son rastreador mas frecuentemente con el robot de busqueda, pero no hay relacion directa entre el PR y esto.
2- Para salir mas rapido necesitas enlaces desde otras paginas. Si no, puedes enviar el sitio directamente desde el formulario de Google, pero va a ser un poco mas lento, y con menos garantias, aunque de esta forma usualmente te incluyen en unas dos semanas mas o menos.
3- No son buenas las altas automaticas. Entre otras cosas la mayoria no funcionan porque los formularios estan protegidos contra altas automaticas, en el caso de los directorios no te podran ubicar en la categoria correcta y la mayoria de los sitios que acepten esto seran granjas de enlaces. Posicionar es una labor que requiere de tiempo y dedicacion, incluyendo este paso del registro.
4- Alta en yahoo:
http://submit.search.yahoo.com/free/request
Sugerencia: Realiza un registro en directorios para comenzar a obtener enlaces utiles a las webs nuevas.