Has the Calendar stopped syncing in both directions or just from BB to Outlook? If it has stopped compeletly check that Wireless Sync in enabled on one of the devices. Open the Calendar and go to Options. Try toggling the wireless sync option to off, save it and turn it back on again.
If Calendar is only syncing from Outlook to the BB then check the following:
1. CDO versions on both the BEs and Exchange. You said that they share a machine so this shouldn't be an issue
2. Permissions - Your BESAdmin must have approppriate permissions in order for the Calendar to sync from BB to Outlook. Also, the BESAdmin cannot be in any admin groups. The only acception is when the BES is on a DC, only then should the BESAdmin be in the built-in Admins group.
BlackBerry Search Results
Calendar data flow works mostly like email. Going from Outlook to BB is the same as email. Going from BB to Outlook is slightly different. The BESAdmin uses MAPI, CDO and Permissions to connect and gain access to the mailbox.
So, typically if the Calendar is not working at all then it's not enabled on the BB or the Desktop[CICAL] service is corrupt. The only way to completely stop Calendar sync on the BES is thorugh an IT Policy and I doubt you would have enabled that.