OK, here it is. I wound up contacting support on this one since it couldn't wait. I had of course re-installed the Exchange Agent on the Veritas box as well as installed the remote agent on the *first node* of my cluster. I did not, however, install the remote agent to the cluster name *mail*, and it also did not appear on the second node of the cluster. Installing and restarting all services did not help, however. I had to modify a registry key entry on the Veritas box as well as both nodes of the Exchange server.
HKEY_LOCAL_MACHINE\SOFTWARE\VERITAS\Backup_Exec\Engine\NTFS
Changed the key *Restrict Anonymous Support* from a 0 to a 1 on all servers involved, restarted all BE services, as well as BE remote agents on both nodes, and walla.
Thanks to everyone for the reply.