La sitemap sembra essere corretta cosi come il file robots.txt che indica agli user agent dei MdR dove trovarla.

Ma le pagine nuove hanno cambiato indirizzo rispetto alle precedenti?

Ho visto che l'operatore site:www.annuncia.it mi elenca una serie di pagine legate alle province che in realtà portano ad un Errore 404, come in questo caso

Hai attivato il redirect permanente, HTTP 301 "Moved Permanently", per indicare agli spider che l'URL è stata trasferita in maniera permanente verso un nuovo indirizzo?

Può darsi che lo spider continui a visitare la vecchia pagina, ma non la trovi più.