This problem occurs because Symantec services require the Microsoft Exchange Information Store to be started before they attempt to start. Symantec's website details a known issue with a timing problem and how to resolve it. Please refer to the following Symantec Knowledgebase article:
The Symantec Mail Security service is stuck in a starting state
The problem may be more likely to occur when Neverfail Heartbeat has been installed because all the Exchange services are set to manual at installation time. Exchange is then controlled using Heartbeat scripts. This behaviour is by default and should not be altered.
Neverfail does not recommended running Symantec Mail Security for Exchange 4.6 without installing the appropriate AMX because Symantec services will remain automatic and attempt to start before the Information Store, this will result in prolonged boot times.
To resolve these issues it is recommended that you follow the Knowledgebase article on the Symantec website to set the dependancies before you install either the AMX or Neverfail Heartbeat. If Neverfail Heartbeat is already installed then it is recommended that perform the instructions provided by Symantec on the active and passive servers.