I had exactly the same problem for a very long time and could solve it with lots of investigation on my side and a liddle help from symantec support. I wana post it here so that you can get rid of the problem faster than I, because it took me several weeks to figure out what was wrong:
My Configuration:
Media Server:
Windows 2003 R2 64-Bit English with Backup Exec 2010
Domino Server:
Windows 2003 R2 64-Bit English with Lotus Domino 8.5.1 32-Bit (without FP)
Blackberry Enterprise Server and Repligo
First we turned on the debugging mode on the Lotus Domino Server with some registry settings provided by the symantec support (I don't remember wich one this where).
For further investigation I used Process Explorer: http://technet.microsoft.com/en-us/sysinternals/bb896653
Then there where Logs created on the Domino Server under C:\Program Files\Symantec\Backup Exec\RAWS\logs every time I browsed the Databases.
SERVERNAME-lnapi0-browse-00.log (For belnapi.exe and belnapi32.exe)
SERVERNAME-beremote01.log (For beremote.exe)
On the printscreen you see there was the Notes LoadLibrary Failed. Error code (c1). That means there is something wrong with the nnotes.dll file.
The log showed that the nnotes.dll could not be Loaded so the Process Monitor was used to search for nnotes.dll
We made sure only 1 nnotes.dll exists on the server (uninstalled Lotus Notes Admin Client from the Server). I tested it out, it has no influence on the server if there are several nnotes.dll files.
It turned out at the end that in my case it was a combination of two problems:
1. Problem: Backup Exec assumed that Lotus Domino was installed in 64-Bit Mode
After the browsing on the media server , the program beremote.exe and belnapi32.exe should be active. The belnapi32.exe is for Lotus Domino 32-Bit, the belnapi.exe is for Lotus Domino 64-Bit.
After the browsing on the Media Server I could figure out with the help of the ProcessMonitor, the belnapi.exe instead of the belnapi32.exe got started (see Printscreen).
Because the registry Key HKLM\Software\Lotus existed, Backup Exec assumed, that Lotus Domino is installed in 64-Bit mode. In the registry there are two keys:
HKLM\Software\Wow6432Node\Lotus (plus subkeys), this key is responsable for the 32-bit Domino.
Solution: After deleting of HKLM\Software\Lotus (and subkeys), Backup Exec knows that Lotus Domino is installed in 32-Bit. (Warning, do a backup of the Key before you delete it)
2. Problem: Something was wrong with the environment variable %Path% in the System
In the Process Explorer it was noticable, that the file nnotes.dll was called with the wrong Path (see Printscreen):
The environment variable Path had a problem. With executing the command ECHO %Path% in the command prompt, it showed a different result than the system field. And a double entry for C:\Domino (that's the path where I installed our Domino Server)
Because the field on the printscreen is to small here the full expression:
C:\Windows\System32;C:\Windows;C:\Windows\System32\Webem;C:\Program Files\HP\NCU;C:\Program Files (x86)\Microsoft SQL Server\80\Tools\Binn\;C:\Domino
--> here the Domino Path appears only once! WTF!!!
Solution: Remove the Path C:\Domino (or where your Domino Server Path is) out of the environment variable Path from the System Properties
I still don't know what happened to the %Path% variable to be different in the System Properties and the command prompt, but at least the problem is solved 
