Здравей,
аз бих започнал с проверка на конфигурацията на ДНС'ите ето един примерен инструмент
http://www.webdnstools.com/dnstools/domain_check . От опитът който имам с местене на майл сървъри и страници от едно ип на друго съм придобил следният похват. Ако кофигурацията е при теб намаляваш следните стойности:
3600 Refresh
600 Retry
1800 Expire
1000 Min TTL
за да може по бързо останалите по веригата ДНС'и да възприемат твоите промени така ще разбираш нещо дали работи или не работи доста по бързо. След като си подкарал всичко да работи както трябва ги връщаш в нормални стойности:
3600 Refresh
600 Retry
1209600 Expire
3600 Min TTL
Относно МХ записите са хубаво нещо да ги има но за тях ще трябва да направиш и СПФ записи за да гарантираш вярноста им след което ще ти пропоръчам да помолиш доставчика ти да направи и ПТР запис за даденият майл сървър.