Если нужно поменять записи MX - переписать почту на другой домен, но это означает что почта не будет работать дня 2-3 - куда будут уходить е-мейлы, и придут ли в новый ящик сами через 2-3 дня?

Некоторое время (до нескольких дней, надо учитывать TTL) потребуется, чтоб новые записи распространились во все края. Клиенты, до которых изменения пока ещё не дошли, будут руководствоваться прежними записями MX, и если те указывают в никуда (на отсутствующий сервер), то почта после непродолжительных попыток передачи будет возвращаться отправителям как недоставленная.

P.S. Если нет возможности обеспечить, чтобы переходное время сервер был доступен и по новым, и по старым записям, то, как Владимир предложил, надо уменьшить TTL старых записей до минимума (но вроде не все регистраторы позволяют), подождать (выждать прежний TTL), пока эти короткоживущие записи распространятся (все будут в курсе, что MX надо освежать часто) и тогда уже вписывать новые узлы.

Если не накосячишь с настройками - всё придёт как надо. В противном случае сендер получит фейл месседж.
Сократи TTL загодя перед сменой записей, чтоб быстренько всё флашнулось, когда уже поменяешь. Посмотри, что говорит ваш Disaster Recovery Plan на случай фейла DNS.
В практике обычно подразумевается, что на такие кейсы будет время простоя: