Постфикс является совместимым RFC и пробует MX самым высоким приоритетом (самое низкое значение) сначала. За одним исключением: кэширование. Если Постфикс встречается, проблема (задержите, отклонение) на первом MX, который это пытается поставить другим. Первый успешный MX будет кэшироваться в течение нескольких часов (я думаю, что это были 24 часа), если кэшируемый MX также не перестанет работать.
Таким образом, если у постфикса появляются Ваши симптомы, это - главным образом ошибка установки DNS или на основе кэширующейся "проблемы".
Вы видите ответ Постфиксного автора к подобному вопросу здесь.