Bueno, si el estado 301 que hemos comentado lo que significa es "redireccionamiento permanente", y creo que google lo que hace es sustituir en el indice la URL vieja por la nueva. Seguirias teniendo el problema de los links desde otras webs a las paginas que ya no existen. Si haces un seguimiento de tus logs, puedes averiguar donde estan esos links e informar al webmaster del cambio.
Y sobre poner el contenido de la index en las paginas que ya no existen, puedes hacerlo. Pero no se si a google le hara mucha gracia. En el peor de los casos, puede tomarlo como una duplicacion de contenidos.
Si tu hosting no te permite redireccion 301 (con .htaccess u otro metodo), creo que lo segundo mejor es crear para cada pagina no existente una con el contenido como por ejemplo, para esteril.html:
<html>
<head>
<title>Esteril: nueva URL</title>
<meta http-equiv="Refresh" content="0; URL=nueva_esteril.html">
<meta nem="robots" content="noindex,folow">
</head>
<body>
La pagina esteril.html ha cambiado de direccion. Ahora se encuentra en <a href="nueva_esteril.html">nueva_esteril.html</a>. Por favor, actualice sus favoritos. Gracias.
</body>
Donde esteril.html es la pagina que ya no existe, y nueva_esteril.html la pagina que actualmente tiene el contenido que tenia antes esteril.html (si es que sigues teniendo esos contenidos, sino la redireccionas a donde tu quieres).
Con el meta refresh lo que haces es que se redirecciones inmediatamente a la pagina destino (la actual). Y con el meta robots, lo que haces es indicarle al robot de google que no indexe (añada a su indice) esa pagina, pero que si sigua los links para indexar las otras paginas.
Con el tiempo, google eliminara de los resultados estas paginas que ya no existen (sibre todo si ya no hay links externos a esas paginas).
Con google hay que tener paciencia.
Suerte.