The RIM tech checked our versions of the cdo.dll and mapi32.dll files on our BES and Exchange server.
The files can be found in c:\Program Files\Exchsrvr\bin
He indicated the cdo.dll on the BES server was not current enough.
They gave the following instructions for updating those files on the BES server:
• Shutdown services on the BES
• Install Exchange SP2 on the BES
• Install Microsoft DST patches on the BES
• Reboot
• Check that the services started back up
• Test if the problem has been fixed

We’re going to apply these changes and will post a follow up.
From the discussion with the tech, there are several other things that could cause this issue, although we didn’t go into those specifically.