Un aporte más al tema: desde hace un tiempo se puede agregar la dirección del sitemap (según el estándar de sitemaps.org) en el robots.txt, de esa forma todas las search engines pueden localizarlo.
Sólo se debe agregar al robots.txt la siguiente linea:
Código:
Sitemap: http://www.sitiodeejemplo.com/sitemap.xml
De cualquier modo, recomiendo hacer el envío de la url a los tres principales buscadores.
saludos!