I am not too familiar with HP policies. How old is the PC? If the PC is less than 3 years old it should still be under warranty in which case they are required by law to assist you with a new disk.
Have you tried using the jumpers to clear the CMOS. The only thing you could hope for is that the clearing the CMOS will wipe out the tag information allowing you to then install an OS.
Also, what you could try is taking the machine to a authorized HP service center. I don't know where you live, but in Chicago, IL area you could go to Computer Discount Warehouse. They have copies of all recovery CD's. If you have proof of purchase they might even burn you a copy. It is worth a try if you have a business like that near you.
It is sad that a company would screw over a potential repeat customer like that. I personally think HP is a pretty crappy PC company. Compaq and Dell are better. HP is better off sticking to making burners and printers.