Backup Exec Deduplication Engine taking a long time to start.
datastore.hdr and datastore.hdr_tlog if found missing from Deduplication Storage Folder\Data\Journal
The Backup Exec Deduplication Engine service could take a long time to start if there are a number of bin and bhd files inside the Deduplication Storage\Data folder when the datastore.hdr and datastore.hdr_tlog are missing.
After the first service startup the above files should get created and this should not be a problem in the next service restart.
Note : If this is the case and server is rebooted, it might take some time for the server to come back up as spoold startup is taking a long time.