@Adam - I'd suggest you contact support and ask them to verify whether you are experiancing the same issue we have been discussing. If so, they will definately be able to provide you with the fix. The KB however is not been published and should be public soon.
Please do not try to involve Exchange 5.5 IMS here when you report the issue. They may need extended support to assist you further. You can simply refer to these two KB articles (931832 & 934450) and let them know that the affected environment is Exchange 2003 SP2. They shoud route you to the appropriate team and support team should be able to verify the issue you are experiancing before sending this fix to you.