Посоветуйте надежный, стабильный, быстрый хостинг. Пробовал много.

Инструкция гугля) http://www.google.com/a/help/intl/ru/admins/resources/setup/

А записи MX поменяйте в панели управления доменом, доступ к которой обязан предоставить Ваш регистратор доменного имени.

Так же поисковая строка самого Гугля предложит множество инструкций по запросу типа: "Как прикрутить домен к gmail" и подобным..

Arion, как раз нахожусь в той инструкции.

Но в панеле управления доменом на nic.ru есть только поля

DNS и IP-адрес. А опции "настройки записей МХ" нет. Или не туда смотрю?

Или нужно Mail Server Configuration менять не у nic.ru а у хостера?

Дело может быть в том, где у вас поднята зона. Зону можно поднимать на серверах как регистратора, так и хостера. Т. е. записи MX возможно менять на тех серверах, где поднята зона.

Arion, а как узнать где она поднята?

Зашел в настройки хостинга, там есть опция смены ДНС МХ.

Сейчас там стоит mx1.spaceweb.ru. - это то самое?

Да, видимо как раз зона поднята на серверах хостера.

Проверить это можно в хуисе)

Только зона может быть у хостера "поднята", а доступа к натсройкам ns-записей он может не давать.

Да, правильно, может и не давать. Это зависит от функционала панели управления доменом.

Иногда требуется отправлять запрос в саппорт с просьбой админов сменить даннные о домене.

Все, разобрался, это действительно было в панеле управления у хостера.

Огромное спасибо за идею на счет gmail, одной проблемой действительно стало меньше.

На VPS рано или поздно все равно будем переходить, но хоть не в такой спешке, как могло было быть если бы почту не починили.