O google re-indexa automáticamente o site. Existem ferramentas do Google para isto. Dê uma iolhada nesta pergunta sobre isso: Como remover um site do Google?
À parte disso eu diria que o google gosta de estabilidade. Um dominio demasiado novo não vai receber muita atênção do Google, por isso mudar de dominio demasiado facilmente é mau.
O que você deve fazer é criar um site map e fazer redirects das páginas que não existem.
Sobre sitemap, é um ficheiro som nome sitemap.xml
que deve estar na toor do site com informação sobre os links do site. Pode gerar um automaticamente aqui: http://www.xml-sitemaps.com/ e depois editar para corrigir detalhes.
O Google tem uma página (em Inglês) bem informativa sobre o sitemap: https://support.google.com/webmasters/answer/183668?hl=en
Fica um exemplo da sintaxe:
<?xml version="1.0" encoding="UTF-8"?>
<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9"
xmlns:image="http://www.google.com/schemas/sitemap-image/1.1"
xmlns:video="http://www.google.com/schemas/sitemap-video/1.1">
<url>
<loc>http://www.example.com/foo.html</loc>
<image:image>
<image:loc>http://example.com/image.jpg</image:loc>
</image:image>
<video:video>
<video:content_loc>
http://www.example.com/video123.flv
</video:content_loc>
<video:player_loc allow_embed="yes" autoplay="ap=1">
http://www.example.com/videoplayer.swf?video=123
</video:player_loc>
<video:thumbnail_loc>
http://www.example.com/thumbs/123.jpg
</video:thumbnail_loc>
<video:title>Grilling steaks for summer</video:title>
<video:description>
Get perfectly done steaks every time
</video:description>
</video:video>
</url>
</urlset>