Принимающие серверы решают судьбу письма по трём вопросам: имел ли право этот сервер отправлять от вашего домена, не менялось ли письмо в пути и что делать, если ответ на первые два — нет.
Пока домен жил на старом хостинге, в DNS стояли записи, отвечающие на эти вопросы про старый сервер. После переезда отправляет новый, а записи остались прежними — формально письма шлёт самозванец.
Второй фактор — репутация. У нового сервера её ещё нет, и первые дни повышенной подозрительности неизбежны даже при идеально настроенных записях.