sidm-
Sorry, I have no idea if the issue occurs with Outlook 2003 clients. We didn't implement the RPC over HTTP when we had an Exchange 2003 server with 2003 clients... we added the Exchange 2007 box, migrated all user accounts to it, then upgraded all clients to Office 2007 *before* even telling them OA was available ;-) So, it was only after OLK2007 users started using OA that I discovered the problem.
The weird part is that even though it is NOW 100% reproducible in my environment, it OA *was* working perfectly with NTLM authentication for a couple of weeks before the problem started. Some Windows 2008 updates did come down around the time the problem started, so maybe that was the trigger...