Backup Exec Fails on Exchange 2003 with V-79-57344-33928 - Access is denied. Error

I have a Windows 2003 environment with Exchange 2003 SP2 running. Last Friday our backups started failed because Backup Exec encountered 5 mailboxes that appears to have corrupt items in them. I am not so sure that they are actually corrupt though.

Backup Exec's job log is indicating that ALL of the Contacts in each of the 5 mailboxes are corrupt and it can't gain access to them to back them up. Below is an example of the several hundred entries in the Backup Exec job log.

Access denied to file Channaile Gordon [cgordon]Top of Information StoreContactsMary Randolph.
The item \\SRV\Microsoft Exchange Mailboxes\Channaile Gordon [cgordon]Top of Information StoreContactsŒ〰〰〰〰慢㜶搶㥦挵㐴㜳㘴㈸㘶㡢㔳㔴慥㍦㌳㜰〰㙥愳捦㉣愰慢愱㔴㙢ㄵ晦挴愴㈷㜵昰〰〰〰㜰㑣收〰〰㜰挴晤㔹㘲摤〶㠴扢ㄲ㐶摦敤挵昳㌹〰〰㌰攷㘳㘰〰〰Mary Randolph in use - skipped.
V-79-57344-33928 - Access is denied.


Access denied to file Channaile Gordon [cgordon]Top of Information StoreContactsDan Pennington.
The item \\SRV3\Microsoft Exchange Mailboxes\Channaile Gordon [cgordon]Top of Information StoreContactsŒ〰〰〰〰慢㜶搶㥦挵㐴㜳㘴㈸㘶㡢㔳㔴慥㍦㌳㜰〰㙥愳捦㉣愰慢愱㔴㙢ㄵ晦挴愴㈷㜵昰〰〰〰㜰㑣收〰〰㜰挴晤㔹㘲摤〶㠴扢ㄲ㐶摦敤挵昳㌹〰〰㌰攷㘳㜰〰〰Dan Pennington in use - skipped.
V-79-57344-33928 - Access is denied.



Access denied to file Channaile Gordon [cgordon]Top of Information StoreContactsMike Miller.
The item \\SRV3\Microsoft Exchange Mailboxes\Channaile Gordon [cgordon]Top of Information StoreContactsŒ〰〰〰〰慢㜶搶㥦挵㐴㜳㘴㈸㘶㡢㔳㔴慥㍦㌳㜰〰㙥愳捦㉣愰慢愱㔴㙢ㄵ晦挴愴㈷㜵昰〰〰〰㜰㑣收〰〰㜰挴晤㔹㘲摤〶㠴扢ㄲ㐶摦敤挵昳㌹〰〰㌰攷㘳㠰〰〰Mike Miller in use - skipped.
V-79-57344-33928 - Access is denied.


It appears that all of these contacts are "in use" at the same time. The job is running at night so no user is accessing all of these contacts at one time.

The only new variable is that we recently bought and installed a Shoretel VOIP phone system and installed the Call Manager software on the Exchange Server. All of the users who are listed in the job log as "failed" with the EXCEPTION of ONE, has the Call Manager software installed on their workstations. So it really doesn't point to the call manager as the culprit of this because there is one user who does not have it installed who is also getting flagged in the job log as having corrupt Contacts.

Any thoughts or insight on where to look or how to approach this?

I thought about doing an Offline Defrag on the Exchange database but was worried that if all of these contacts were corrupt, it would delete all the contact records in the database. That is something I don't want to do.