When you configure a job to use hardware compression in Backup Exec, BE just sends a signal to the tape drive to perform hardware compression. It is then up to the firmware on the tapedrive to use the algorithm on the chip in the tape drive to compress the data. BE has nothing to do with it at that point.
Check the Soft-write errors in Properties|Statistics for the tape drive in Backup Exec. If you have a lot, they can seriously erode the capacity of your tapes. How you ask? Every time a tape drive encounters a soft-write error, it is fast-forwarding past what it thinks is a bad spot on the tape. Enough of those errors occur and you are fast-forwarding through much of the tape, decreasing the amount of data that can be written to the tape.
Check the same statistics on your tape. Try new tapes. Make sure HP didn't send you a 'refurbished' tape drive. Also check to make sure you are using the most optimum settings for block size, buffer size, etc on that tape drive. Contact HP for those settings.
Good luck!