Eric,
This may not apply to your case, but in hopes that it does...  We had orphan 
entries in our database that were confined to storage records.  I believe TSM 
Support was able to discern that from the error messages we were seeing in the 
Activity Log.  That allowed us to do the audit on the storage records only, 
(auditdb diskstorage fix=yes)  and that ran much faster than a full audit.  In 
addition, we  cleaned all data from the disk pools before starting the audit, 
and that accelerated the audit by a factor of 10 to 1.

Best wishes,
Keith