Для начала нужно проверить тип авторизации (Basic\NTLM) в настройках профиля. Сравнить имена сертификатов используемых серфисом реально и предоставляемых Outlook Provider в настройках Autodiscover (для этого надо запросить информацию Autodiscover при помощи функции Outlook "Проверить автоконфигурацию электронной почты", которая вызывается при щелчке левой кнопкой мыши на иконке Outlook в трее при зажатой клавише Ctrl). Еще проверьте Autodiscover и Outlook Anywhere при помощи МС-овского тестера подключения (
http://testexchangeconnectivity.com), он дает очень много диагностической информации. И когда вы эту информацию соберете - вот тогда возможно появится повод для намека хостеру.
Самое главное в услугах хостинга - Zero Touch Expuatation. Т.е. запуск с минимальными действиями со стороны клиента. Вы можете хостеру намекнуть, что у вас постоянно просит пароль - и пусть его ребята сами ломают голову (Delirium правильно предположил проблему с авторизацией на стороне хостера, я скажу больше - проблема с сертификатом безопасности и типом авторизации).
