En general cuando un sitio está caido tarda unos días en recuperar posiciones, puede ser casualidad. Puede ser que el nuevo alojamiento no "fuera tan bueno" a ojos de Google.
Puede ser que (esta es la opción que considero más probable) al estar caido x días y volver a aparecer en otra ubicación Google os tenía en "cuarentena", por si fuera un robo o algo sospechoso, al recuperar las ips antiguas desapareció la cuarentena.
