А на сколько вы продвинутый пользователь? Я бы предложил диагностировать проблему отправив письмо руками на сервер через telnet. (Помогать смогу после 8 UTC, сорян)
Могу разобраться, но звучит чрезмерно.
Почта-то Exchange MX. Домен один, на нём много почтовых ящиков.
Отправляю на неработающий с разных -ничего не приходит.
Квоты в админке нет. Через веб-интерфейс письма не видны.