After looking into this, it looks as if Microsoft have updated their Exchange backend version without telling anyone, which has caused this issue. Whilst there's no update available through Veeam at the moment, logging a support case with them provided me with a fix to get this up and running.
The error message in question here states "Invalid Exchange Server version". This starts to fail for most mailboxes, and will eventually fail for all mailboxes. Obviously this is a P1 issue, as you don't have backups up and running.
The fix is only available if you're running version 1.0.0.912, and is the following:
Download the hostfix file from https://storage.veeam.com/Fix_113114_fbcf2c440c.zip and follow the instruction to apply
the hot fix.
The workflow:
- Stop all the jobs
- Stop “Veeam Backup for Microsoft Office 365 Service”
- Rename and replace Veeam.Ews.dll with the DLL from the archive in C:\Program Files\Veeam\Backup365 (don't forget to back up the original DLL)
- Start “Veeam Backup for Microsoft Office 365 Service”
- Retry the job
After performing this fix, it has 100% resolved the issue for my clients.