Muchas gracias a todos por las respuestas.
Lo de la página de error 404 personalizada ya la puse gracias a una contribución. La pena es que no puedo hacer redirecciones 301 porque no siguen ningún patrón, por lo que voy a tener que eliminarlas de una en una. Llevo unos días en los que voy hacia atrás en el ranking de Google y quizás esto me esté influyendo negativamente. Eliminaré también lo del robots.txt ya que como sospechaba no iba a valer para nada.
Me edito para hacer otra consulta, estoy eliminando las páginas y he visto que te da la opción de eliminar directorio, si elimino el directorio /tienda, se me eliminaran las otras mil páginas que son /tienda/ejemplo ?
Me ahorraría bastante trabajo jeje ya que parte del cambio de las urls es porque el directorio tienda se eliminó.
Un saludo.