[QRS]

В первую очередь можно проверить на шлюзе - имеет ли место входящий трафик SMTP.
Если да - копайте свой Exchange (может он все в спам гонит ), если нет - начните с MX записи, а затем файрволов (своих и провайдера).