Actually, your bpbkar log indicates a 6.5 client. Is this right?
8:06:26.368 AM: [5128.5016] <4> ov_log::OVInit: INF - the log mutex: 536
BPBKAR NetBackup Backup/Archive 6.5GA [Jan 4 2010]
Copyright 1993 - 2007 VERITAS Software Corporation
All Rights Reserved.
That may be why I wasn't seeing the logs I was expecting.
The TechNote for hostname truncation is now available:
STATUS CODE 69: Exchange hostnames greater than twelve (12) characters may be truncated in NetBackup 7.0, causing backup failures as well as failures enumerating backups taken prior to an upgrade to 7.0.
http://support.veritas.com/docs/357299
I'm not sure how this issue would manifest itself in a mixed environment, but I still think that given you are getting the same status code AND you have a hostname longer than 12 characters, this may still be the way to attack this.