ローカルのExchangeサーバー（たとえばSBS2011）から、Office365のExchnage Online に移行をした場合、
いつも通りにOffice デスクトップ アプリケーションをインストールしてOutlookを起動すればOKとはなりません。
AutoDiscoverがローカルのExchange サーバーを参照してしまい、ExchangeOnlineへ接続できません。
下記レジストリを編集することで、きちんとOffice365を参照するようになります。
これはSBSのExchangeの利用は停止するけど、ドメインコントローラ、DNSサーバーとしては引き続き利用する場合などに起こる現象です。
（DNSサーバーの設定を適切に変更すれば解決するかもしれませんが…）
詳細はコチラを参照してください。
参考：Exchange Online の試用期間中または Exchange Online と Exchange Server 2007 との電子メールの共存期間中に問題が発生する(KB956955)
先日、リンク切れだったので、対処方法だけメモします。原因などはリンク先をきちんと参照してください。
以下のレジストリサブキーを探して、 HKEY_CURRENT_USER\Software\Microsoft\Office.0\Outlook\AutoDiscover 以下のレジストリ値を設定します。 値の名前 : PreferLocalXML 値の種類 : DWORD データ : 1 値の名前 : ExcludeHttpRedirect 値の種類 : DWORD データ : 0 値の名前 : ExcludeHttpsAutodiscoverDomain 値の種類 : DWORD データ : 1 値の名前 : ExcludeHttpsRootDomain 値の種類 : DWORD データ : 1 値の名前 : ExcludeScpLookup 値の種類 : DWORD データ : 1 値の名前 : ExcludeSrvRecord 値の種類 : DWORD データ : 1
レジストリの編集には十分気を付けてください。
インストールしているOfficeのバージョンによってはレジストリサブキーが異なります。
※SBS2011についてはこちらのリンク Windows Small Business Server 2011 を参照してください。