Hola Hechizero, personalmente me ha ido siempre muy bien con google ,hace justo una semana que publiqué una web, y a los 5 días me indexó google (ahora parece que han hecho cambios y hay minidances). En cambio hay otros buscadores con los que no hay manera (alltheweb me tiene manía
).
Lo más rápido con google es (además de que te pongan un enlace una web ya indexada,... y si esta es importante mejor): encontrar a través de google directorios de tu temática, pero que no sean importantes (no te filtran y te indexan casi el mismo día)...google no tardará casi nada en indexarte (hablo de días). Luego ya vendrán directorios decentes donde cobrar importancia.
Por lo menos con google si sigues unas reglas, tienes grandes posibilidades, en el resto (por el procedimiento gratuíto) sólo puedes cruzar los dedos.
Un saludo