One of the most interesting aspects of working with services as opposed to a bits on disk product group, is that we update capabilities all the time. That's really different than releasing service packs for features updates. One of the updates we released was adding Outlook 2003 as a client for Exchnage Online. Since Outlook 2003 was released before autodiscover was created, it is missing free/busy capability and GAL lookup when used in the online environment. Well, that just won't do.
There is currently a beta of the Outlook 2003 free/busy connector that you can sign up for. See the link below for details.