I've made a little progress - I have not yet updated MAPI/CDO, but did do a network capture. At the time we got this error in the ALRT log:

[30000] (02/10 02:14:13.728):{0x20A4} [Alarm::ActivateAlarm] Queuing alarm: <N/A> | BlackBerry Messaging Agent BESServer Agent 1 (Application Event Log on BESServer.domain.local) | 02/10/2013 02:14:13 (EFFF2825) -> BlackBerry Messaging Agent BESServer Agent 1 failed to start. Error code 5305

The network capture recorded:

1064653 2:14:13 AM 2/10/2013 8963.3886465 BlackBerryAgent.exe CAS.Domain.Com BESServer MSRPC MSRPC:c/o Fault: Call=0xE Context=0x0 Status=0x1C010014 Cancels=0x0 {MSRPC:11522, TCP:11520, IPv4:7}

That status (0x1C010014) indicates the server (one of the CASes) is too busy to fulfill the request.

Combine this with the IOS 6.1 issues with Exchange we're seeing, and I wonder if they're not related, since that update was released a day before we started seeing issues.

Anyway, we'll see what I find out next. Just need to collect some perf logs from the CASes.