J'ai fait une mise a jour d'un site, en fait un rewrite from scratch, toute l'arboresence et tout les noms de pages ont change.
 
J'ai pris le "Top 30 entry pages" dans les stats et j'ai fait un .htaccess avec des RedirectPermanent vers les nouvelles pages. Ca marche bien j'ai quasiment plus de 404 dans les logs.
 
Par contre y'a un truc que je sais pas, c'est combien de temps les anciennes pages vont rester dans le cache de Google.
On voit bien dans les logs que GoogleBot passe regulierement mais si je fait une recherche site:www.monsite.com je n'ai toujours que les anciennes pages, ca fait 10 jours que la nouvelle version est en ligne.

Ca dépend, faut que Google mette à jour son index. C'est assez aléatoire, mais en général si au bout d'un mois c'est pas à jour, c'est qu'il y a problème