I am having the same problem. I set all BackupExec services to start manually, rebooted the server, started SGMON.exe and tried to start the BackupExec Server service and here is what I get relating to "beserver" from sgmon.exe:
Capturing to C:\Program Files\VERITAS\Backup Exec\NT\logs\SGMon.log
beserver: 01/09/06 15:17:24 -1 Starting beserver system service application
beserver: 01/09/06 15:17:24 -1 Entered RpcXfaceServiceMain.
beserver: 01/09/06 15:17:24 -1 Sending start status to scm. (hint 300000)..
beserver: 01/09/06 15:17:24 -1 Initializing ACE...
beserver: 01/09/06 15:17:24 -1 Cblmanger, shutdown Immenient: started.
beserver: 01/09/06 15:17:25 -1 Cblmanger, shutdown Immenient: complete.
beserver: 01/09/06 15:17:25 -1 Cblmanger, check shutdown Ready: started.
beserver: 01/09/06 15:17:25 -1 Cblmanger, check shutdown ready: complete.
beserver: 01/09/06 15:17:26 -1 Initializing work queue...
beserver: 01/09/06 15:17:26 -1 Initializing Persistent Store (GVLNAV\BkupExec, BEDB, Backup Exec Server, 30 seconds)...
beserver: 01/09/06 15:17:26 -1 Attemp to GetMyPartition ComputerName=GVLNAV PartitionID=0 PartitionGUID=c3a0b6d5-86ce-4344-a26a-38f81ef49db8
beserver: 01/09/06 15:17:26 -1 InitializePartition() Data partition ID from registry=0
beserver: 01/09/06 15:17:26 -1 GetMyPartition() Data partition to use for 'GVLNAV' is 0
beserver: 01/09/06 15:17:26 -1 InitializePartition() returning 0x0
beserver: 01/09/06 15:17:26 -1 Successfully GetMyPartition ComputerName=GVLNAV PartitionID=0 PartitionGUID=c3a0b6d5-86ce-4344-a26a-38f81ef49db8
beserver: 01/09/06 15:17:26 -1 InitializePartition() ok, partitionID=0, oldComputerName=
beserver: 01/09/06 15:17:26 -1 Creating Business Objects...
beserver: 01/09/06 15:17:26 00 VSN BO Initialization succeeded.
beserver: 01/09/06 15:17:26 -1 FillServerInfo: cw.Open() failed.
beserver: 01/09/06 15:17:26 -1 ServerName:GVLNAV, ActiveNodeName:,
InstanceName:BkupExec, DatabaseName:BEDB.
beserver: 01/09/06 15:17:26 01 Server Configuration: BEServer schema version checks OK.
beserver: 01/09/06 15:17:26 01 Server Configuration: Initialization Complete.
beserver: 01/09/06 15:17:26 02 Ownership: Initialization Complete.
beserver: 01/09/06 15:17:26 03 JobManBO: starting initialization...
beserver: 01/09/06 15:17:26 03 JobManBO: initialization complete...
beserver: 01/09/06 15:17:26 04 CAuditLogBO: Initialization completed.
beserver: 01/09/06 15:17:26 05 LoginAccount: Initialization Complete. BO=5.
beserver: 01/09/06 15:17:26 06 Resource: Initialization Complete.
beserver: 01/09/06 15:17:26 07 ServersBO: Initialization Complete.
beserver: 01/09/06 15:17:26 08 CMediaServerPoolBO: Initialization completed.
beserver: 01/09/06 15:17:27 09 ScriptMgrBO: Initialization Complete. BO=9.
beserver: 01/09/06 15:17:27 10 MessageQueue: Initialization Started.
beserver: 01/09/06 15:17:27 10 (3380) ( 15:17:27.111000) CManager started Logging
beserver: 01/09/06 15:17:27 10 (5188) ( 15:17:27.158000) MSGQ EventManager started.
beserver: 01/09/06 15:17:27 10 (5272) ( 15:17:27.158000) CWorker started.
beserver: 01/09/06 15:17:27 10 MSGQ Data File: 0: msgq0000000000.dat
beserver: 01/09/06 15:17:27 10 (3380) ( 15:17:27.205000) MSGQ Data using Persisted File.
beserver: 01/09/06 15:17:27 10 (4144) ( 15:17:27.174000) CWorker started.
beserver: 01/09/06 15:17:27 10 MessageQueue: Initialization Complete.
beserver: 01/09/06 15:17:27 11 Djm: pMMSFeature is NOT installed, setting mmsUsable FALSE.
beserver: 01/09/06 15:17:27 11 Djm: pCASOFeature, CASO installed:1, CASO enabled:1, LicenseInfo CASO authorized:1.
beserver: 01/09/06 15:17:27 11 Djm: casoUsable: TRUE
beserver: 01/09/06 15:17:27 11 Djm: Caso is usable, setting mmsUsable to TRUE.
beserver: 01/09/06 15:17:27 11 Djm: QSendInvals Reg: JobResQ:10, Conf:2, JobQ:2, Alrt:6, Vsn:2.
Based on articles in the Knowledgebase, so far I have tried 1. Uninstalling and Re-installing Microsoft Office Outlook & 2. Removing and re-creating the e-mail profile for Microsoft Office outlook.