I would be very surprised that Backup Exec would be deleting the public folder.
In Exchange 2000 Server and Exchange Server 2003, an administrator can enable the auditing of public folder deletion by adjusting diagnostic logging for the Public Folders General category to Medium or High. This comes from
http://technet.microsoft.com/en-us/library/bb123804(EXCHG.65).aspx. I suggest you enable this feature.
If you think Backup Exec is the culprit, make sure to create a separate service account for Backup Exec. That would make it simple to determine if it's Backup Exec deleting the folder or not.