Have you checked the Application and system event logs to see if you have nay other events that point you to the root cause of the problem?
Would be possible to uninstall and reinstall NMM? Please note that if you have GLR installed this (uninstall and install) will require to reboot twice.
Uninstalled, reinstalled, get the following error from NetWorker in the Application log; mapi(5056): Could not open EMS Store for Exchange Server SVR01, status 0x80040115.
Repairing/re-installing the CDO has no effect.
The status code "0x80040115" equates to MAPI_E_NETWORK_ERROR. This can often be caused by permissions or possibly CAS-related issues.
Can you ensure that the service account has all required permissions (mainly Backup Operators, Exchange Servers, Organization Management) as well as Send-As/Receive-As permissions? Since you mentioned this issue only began occurring recently, I assume the account already has all of these.
Also, have you tried pointing to a different CAS server? I have seen issues with hardware load balancers causing browsing to fail, and they were resolved by pointing to an individual CAS server instead of the array name. This can be changed in the GUI, as seen in the attached screenshot.
There has also been a previous instance where this same error was generated due to the alias of the NMM service account being the same as another AD account in the environment. We could eliminate this as a culprit by creating a new AD account, providing it all the required permissions, mailbox, etc, and then using it as the service account. This obviously takes more effort, so maybe try the other two steps first