We have the same problem.
Reapplying the Blackberry patch or Exchange SP2 fixes it for a while, but it comes back very quickly.
All the CDO.DLL files are the same.
We have also tried turning the Blackberry server off, this fixes the problem.
There are several posts about this but I cannot find an answer to it.
Anybody got some more ideas, we need to get this fixed.