Error 0xe0008516 backing up Exchange 2013 after applying BE 15 "Feature Update 1"

We are running a single Exchange Server 2013 SU5 running on Windows Server 2012 R2

Backup provided with BackupExec 15 (14.2 rev 1180) running on Windows Server 2012 R2

All went well until we installed the recent Backup Exec "Feature Update". The Exchange backup fails with

Auftrag beendet am Mittwoch, 16. September 2015 um 13:45:38 Abschlussstatus: Fehlgeschlagen Endgültiger Fehler: 0xe0008516 - Die für den Snapshot angegebene Datenbank wurde nicht gesichert, da die Datenbank nicht bereitgestellt war. Endgültige Fehlerkategorie: Systemfehler Zusätzliche Informationen zu diesem Fehler finden Sie unter der Verknüpfung V-79-57344-34070

The linked KB article leads nowhere.

Exchange itself runs without any problems and certainly the database IS provided.

I upgarded all agents and tripple checked the login configuration, rebooted both the backup server and the exchange server. I even created a new full backup job that only selected the entire "Exchange Information Store" with a single "Mailbox Database" and "PublicFolder Database".

Same Error

I did a thorrough research that resulted in "check your VSS writers" most of the time, so  I checked the VSS writers with

vssadmin list writers

and I get a list of healty writers, but there is no “Microsoft Exchange Writer” listed as is presumably shuld(?)

• There is NO "exwriter.dll" anywhere on this server and since I doubt the Backup Exec Feature update deleted this one, i'm confident that there never was one.
• I DO have a "Microsoft Volume Shadow Copy Provider" service and if I start that one manually, it shuts down "clean" a few minutes later without any complaint.
• I DO have a "Exchange Extension for Server Backup" sevice that does quite the same.
• I CAN make a backup with the standard windows backup which successfully utilizes VSS
• Neiter the event log on the Exchange server nor the one on the backup server show anything useful

I tried with and without the "granular" option.

I'm quite clueless now how to proceede. The backup log is attached for a full backup from before the update that went well and one after the update that failed.

Thanks for any help on this,
Robert