Honestly, using Server 2003 on Exchange, which is what I assume you are on, is something I wouldn't do. I would be on Server 2008. We are on Server 2008 and have no issues with such things.
I know easier said than done, but maybe someone else has a workaround for you, but i'm thinking you might have hit the nail on the head.