This is weird. Ok, do they stop during a backup? If so can you post up the backup log.
Also, you should be able to see the backup exec services stopping in the event logs, can you see that
Does the server reboot at all?
You can try running backup exec in debug mode and then check the logs when it happens again (see link below):
http://seer.support.veritas.com/docs/254212.htm
or
http://seer.support.veritas.com/docs/250681.htm
Other options of the top of my head are the usual things, like instal the latest service pack, run a repair of backup exec, repair the database etc.