Ziptar

У gmail есть ограничения по выгрузке данных из сервиса, причём разные для pop и imap. Просто подождать пробовали день-другой?
Ну и просто банально попробуйте отключить imap в настройках gmail и включить обратно - была, помнится, какое-то время назад проблема с выгрузкой почты с gmail, которая решалась именно этим способом.

Копать в сторону того, правильно ли указывается адрес отправителя в заголовке письма, т.к. gmail видит адрес вида username@com, а такой адрес валиден быть не может по очевидным причинам.

Бесплатные ящики gmail, MTA (Postfix+SASL) на VPS. Для пересылки на адреса домена Postfix'у ничего не нужно, для отправки с адресов домена как раз и нужен SASL. Gmail позволяет отправлять письма "send as" с аутентификацией по логину/паролю.
Для отказоустойчивости - 2-3 таких vps у разных хостеров.

Из плюсов - MTA локально почту не хранит (только на время пересылки), поэтому каких-то особых мощностей не нужно. БД тоже не нужна. Почтовые клиенты тоже не нужны - только бесплатные ящики любого популярного сервиса. Из минусов - бэкапить придётся вручную отдельно каждый ящик, если это вообще нужно.