I've been using Outlook 2003 for quite awhile now and have no problems with synchronizing. Using AS 3.8, XP pro, Dell X50v.
But I'm not using EMail on my Axim.
I do remember seeing the same problem you are having, but can't remember where or when.
Suggest you search on Microsoft's knowledge base and also Google. I remember it was some real strange circumstances that causes the problem.
Wish I could be more help.