I can offer some solutions one or a combination of which will hopefully correct the error.
First, check your BIOS settings to see if S.M.A.R.T drive reporting is enabled. If it is, disable it and give it a test run of 2-3 days under a regular rebooting cycle to see if the error persists. S.M.A.R.T. (Self-Monitoring Analysis and Reporting Technology)is a somewhat outdated standard developed as an "early warning" system to detect hard disk issues. If your desktop is newer, it may not even be available as an option as it is not widely used these days. The SMART technology while useful under certain circumstances had an extremely wide margin of error and would throw errors on boot occasionally when there would be nothing from either a physical or configuration standpoint failing or pending failing in the drive.
While we're in the BIOS, I'd recommend that you ensure that it is recognizing the drive correctly on each startup. The easiest way to ensure this is to reset your BIOS default settings. While on the BIOS screen, look for an indication either along the top or bottom designated by one of the function keys (I believe it used to be F10 to restore defaults). Be sure to save your changes and exit. Again, where you did not get the error every time, you may need to monitor it's progress to see if the error returns.
Second, physically check all cabling. A loose or in some cases failing IDE cable (assuming it is an IDE and not SATA connection) will produce these errors in the Pavilion line (and most others I would well imagine). Power everything completely down, remove the side of the case to give access to the drives and start with reseating the cable both at the drive end and the controller (where they plug into the motherboard) ends. Ultimately, if you were to pick up (or could somehow borrow) a different IDE cable to test for a short time it may also call out a failed or failing cable as well.
Third, we can't overlook the possibility of a failed drive itself. Formatting and/or recovering the drive will most likely not correct an error of this type. If any of the steps on the HP forums resemble those suggested above and have already been attempted, the issue may well point to the disk itself. How old is your system out of curiosity. HP had a now-infamous recall issue back at the early part of 2001-2002 with a batch of Fujitsu brand hard disks. Although I am skeptical that there are still some of those offending drives floating around (and if so that you are only receiving errors 6 years later :)), the company *are* still obligated to replace should the drive be determined to be part of this recall. I realize this option is quite a stretch given the timeframe.
Keeping with issues with the drive itself however, if all steps listed above don't correct the errors, there could be a strong possibility of a failing disk. Since you say it will boot on occasion the failure may not be severe enough at this stage to completely fail, but a total inability to boot may be looming on the horizon. If the system is still within the warranty, HP will replace the drive for you (you will most likely have to ship the tower to them in a postage-paid box they will send you if you are unfamiliar with the repair process).
Should the system be outside of any manufacturer or extended warranty you may have purchased additionally, you will need to purchase and have a new hard drive installed. Some facilities may be able to salvage information off your original disk for transfer (although where you are still at a point where your OS boots occasionaly, backing up data important to you is something I would go about starting ASAP) before installing the new one.