I’m a little fuzzy on the details here, but I believe Outlook 2003 started prompting for a password, which it shouldn’t do because the user was logged on the domain and the password should have been autosubmitted to Exchange 2003.
Changed the security settings to use NTLM password authentication, which means that the password autosubmitted to Exchange will be the one used in the Network logon. Works fine now.