La soluzione è spostare il dominio vecchio e ben posizionato sull'hosting nuovo, mantenendo ovviamente lo stesso sito come prima. Il nuovo dominio lo metti in redirect sul vecchio per eliminarlo dall'indicizzazione.

Il cambiamento del puntamento dei redirect è un'operazione indolore, ovviamente dipende da come la fai... bisognerebbe tu potessi agire sui dns del dominio senza spostarlo di mantainer e fare in modo che l'hosting di destinazione sia configurabile a prescindere dal dominio.