Bueno, a mi, me ha dado mejores resultados tener varios sitemaps pequeños que uno grande, uso uno para cada país:
http://www.elquick.com/clasificados-...categories.xml http://www.elquick.com/clasificados-...categories.xml
....
cada 1 tiene 114 links, antes tenía uno bastante grande y pos indexaba muy pocas páginas (ni siquiera la mitad) y con los pequeños todo va mucho mejor ... solo quedan más o menos 30 url's sin indexar.
Recomiendo varios sitempas pequeños pero bien organizados por algo en común.