Прежде всего, вы убедились, что код работает с другими почтовыми серверами?
Некоторое время назад кто-то упомянул, что у него были проблемы с определенными серверами, принимающими http-запросы с компонентом Indy TIdHTTP. Причиной было то, что они включили Indy как часть useragent:
Request.UserAgent := 'Mozilla/3.0 (compatible; Indy Library)';
Когда они удалили Indy Library это сработало. Очевидно, были некоторые злокачественные веб-сервисы, созданные с помощью Indy, поэтому некоторые сайты будут отказывать в соединениях из приложений, созданных с его помощью.
Я не уверен, что используемый вами компонент имеет какое-либо свойство UserAgent. Но если это произойдет, обнулите любые ссылки на Indy.