A ver si entendi, tu solicitaste la baja del servicio de hosting y por ello te lo dieron de baja? Al devolver el recibo como mencionas solicitaste la baja. En ese caso no veo el porque del cambio de hosting. Simplemente como hiciste, debes volver a abonarlo y se te dara nuevamente de alta.
Con respecto a recuperar el posicionamiento... lo que seguramente vas a recuperar es la indexacion de tus urls en google. Es decir google volvera a mostrar tus urls en tus busquedas. Podes ver que urls google tiene indexadas actualmente buscando por: site:
www.tudominio.com
Esto es muy distinto a recuperar el posicionamiento. Esto dependera en su mayoria del algoritmo de google y de la calidad del contenido de tu web en comparacion con el resto con la misma tematica.
Saludos.