[Oleg Krylov]

Для начала нужно увеличить уровень диагностики службы до максимального уровня (Debug (7)). Для этого откройте ветку реестра HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\MSExchangeMTA\Diagnostics и всем ключам в ней присвойте значение 7 в десятичной системе счисления.
После этой операции, и последующего запуска служб в логах должны появиться дополнительные диагностические сведения.
Затем, я бы посмотрел на количество свободного места на дисках, особенно на диске, на котором лежит каталог MTADATA.
Далее, проверьте от имени какой учётной записи запускается служба. В идеале от Local System.
Проверьте тип старта, должен быть Automatic (бывает тип старта сбрасывается).
Хорошо бы уточнить версию сервера и его окружение (наличие Exchange 5.5 в группе маршрутизации, коннекторы для LotusNotes, Novell GroupWise, а так же прочие сторонние коннекторы, например ПО, позволяющее отправлять факсы). Если это Exchange 2003 в native mode и нет вышеописанных особенностей окружения - службу можно отключить. Подробнее здесь: http://support.microsoft.com/?kbid=810489
Для Exchange 2000 отключение службы не поддерживается Microsoft.