[Vich]

mx=mail.host.kiev.ua, но есть еще A запись mail.host.kiev.ua, которая вероятно указывает на старый ip. Ее тоже нужно поменять