OK, so for starters I would get your environment updated.
Install SP2 on Exchange 2003.
If you instaleld the Exchange Tools on the DCs then you need to also install the SP on the DC.
Install Outlook 2003. EACH Exchange CAL comes with a free Outlook 2003 CAL, so you will not be breaking your licensing by installing Outlook 2003.
you can automate the install of Outlook 2003. Refer to my FAQ on the subject faq96-4996. Note that the FAQ was written for Office, but same steps apply to just setting up Outlook.
Also above you did not note if you checked if they are working offline.
I hope you find this post helpful.
Regards,
Mark