вылезает ошибка "Методы аутентификации не поддерживаются сервером"
что есть в логах Exchange по этому поводу?
1. ЕМНИП - в Exchange 2010 есть два дефолтных Receive Connector:
Default SERVERNANE (слушает 25 порт и принимает почту из интернета) и
Client SERVERNAME (обычно слушает 587 порт и принимает почту от клиентов типа POP3/IMAP4 для дальнейшей отправки).
У вас сломался второй. В настройках коннектора есть вкладка Permission Groups - вдруг кто-нибудь менял настройки в последнее время?
2. Сертификат в системе никакой не протух?
3. Обновления (внезапно) никакие не ставились - на систему, Exchange?
3. На внешних файрволах менялись настройки?
4. Проверьте настройки TLS и алгоритмов шифрования (2010/2013 максимум могли в TLS1.2, а по умолчанию оно отключено). Ну и, соответственно, "на новом Android устройстве" устаревшее шифрование вполне может не работать.
На компьютерах и айфонах такой проблемы нет
не показатель, ибо мы не знаем, что вы используете для подключения (версия Windows, какие почтовые клиенты и т.д.)
З.Ы. У клиента GMail есть встроенная возможность подключения к Exchange (при настройке можно выбрать) - зачем IMAP? (если только это не настоятельная хотелка или следствие неполноценной настройки)