Today Microsoft released the Microsoft Exchange Online Connector for Outlook 2003 version 1.0. With this connector you can connect to Exchange Online using Outlook 2003 for free/busy lookups and to download the offline address book.

Be advised that the connector is not supported on Windows 7 or on any x64 version of Windows.

You can download the connector here.