Тема старая, пострадаю некрофилией. Учитывая, что за 2 года никто так и не ответил...
Если удастся перенести ящики пользователей (о чем говорил предыдущий оратор) на новый сервер, достаточно будет на локальном ДНС сервере прибиндить mail.nic.ru к pop.yandex.ru. Для этого объявляешь матерзону nic.ru, переносишь в неё записи с реальной зоны, кроме mail, а для mail делаешь CNAME на pop.yandex.ru.
Вместо pop.yandex.ru можно использовать smtp.yandex.ru - у них адреса совпадают.