Backup Exec attempted to back up an Exchange database according to the job settings. The database was not found

Hi,

I am having a hard to figure out this one, so I am reverting to the experts ;)
Hope you can help me on that one.

We have a Backup Exec 2012 server on the same physical machine as our Exchange2010/DC server. I know, I shouldn't have ;)

We've been without a successful backup of this critical server for a few weeks now. There was another blocker before, but for a few days now, the backup states it cannot find the only MailboxDatastore we have.

Backup Exec attempted to back up an Exchange database according to the job settings. The database was not found

V-79-57344-913 - Backup Exec attempted to back up an Exchange database according to the job settings. The database was not found, however. Update the selection list and run the job again.

BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.373 [ndmp\ndmpsrvr] | Backup Job Starting
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.374 [ndmp\loops] - The media server PDC is already in the advertisement list.
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.374 [fsys\ese] - [ESE_AttachToDLE] device_name:\\pdc.processia2003.com\Microsoft Information Store\Mailbox Database 0056630370 attach_reason:0x21 backup_type:4
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.374 [fsys\ese] - [ESE_ValidateBackup] Mailbox Database 0056630370 enter ...
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.374 [fsys\shared] - Monad RPC timeout 300000
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.374 [fsys\shared] - EseProcess::Init: OpenThreadToken successful
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [fsys\shared] - ESE07 Create process returned 522
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [fsys\shared] - ESE07 process not ready
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [fsys\ese] - [ESE_ValidateBackup] exit (0xe000ff21).
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [ndmp\loops] - LP_ENV::MsgError: error 0xe000ff21 processing object <Unknown>
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [ndmp\ndmpsrvr] + ndmp_data.cpp (13051):
 BEREMOTE: [03/05/14 13:52:13] [10608] 2014-03-05T13:52:08.375 [ndmp\ndmpsrvr] | Backup Job Stopped(0)
 BENGINE: [03/05/14 13:52:13] [5236] 2014-03-05T13:52:08.375 [server] - Test Run Error: e000ff21

Every BE service is running under the domain administrator account
It is configured as the system account in BE.
Assigned to the job.
The administrator account has Organisation management rôle in Exchange and is member of Back Operator group, as well as Domain Admin group.

The credential tests fail on the Mailboxstore in BE.

I rebooted the server.

vssadmin list writers gives me all stable writers.

Tried this :
http://www.symantec.com/business/support/index?page=content&id=TECH209154&actp=search&viewlocale=en_US&searchid=1394030905270

Tried those too :
http://www.symantec.com/business/support/index?page=content&id=TECH140090

Only thing I am seeing, is that the domain Administrator is not a local admin on the DC, as there are no local admins on DCs.

Any hint ?

Exchange is @ SP3, but not roll update 3, should I ? (Knowing I don't have a good backup in case of a problem)

Thanks for your help !