There are many reasons for this problem. Most are related to COD.dll.
luckey's solution seems like it was probably fixed in CDO code in MS Exchange SP2.
tc490225's script to remove the temporary _COD profiles is a great way to work around the problem, and other calendar related problems (ofter permissions related).
Anyone having this problem will have to give more details.
What is your BES version, what is the Exchagne System Manager version on the BES?
What is your backend Excahgne version?
Is full Exchange on the BES, or the Exchagne System Manager?
What Outlook versions do the users use? (or what is the highest version they may use?)
What is the cdo.dll version on the BES?
How many cdo.dlls are on the BES?
Which one is the registered one?
How To - Check if and where the CDO.dll file is registered
KB04912: BlackBerry Search Results
Determining which CDO version should be installed on the BlackBerry Enterprise Server
KB10197: BlackBerry Search Results