We have some old Compaqs at work here... They had the "Utility partition" on the HD, which (if there) would let you into the BIOS.
If you've formatted the HD, chances are the "Utility partition" is gone.
Not all hope is gone! Compaq has a couple of diskettes you can boot of off and it will act as that "Utility partition" or even install it for you.
(At work, I opted to make the "Utility partition" and then image the rest of the HD. This way, I wouldn't have to carry around a couple of diskettes in order to access the BIOS.)
I'll search around for the diskettes. PM me if you want an image of them. You should be able to download them off of Compaq's site (whoops, I mean, HP's site). Good luck finding them through!