I'm not sure why you can't "Add" it except that if it can't find an appropriate driver, it won't allow the printer access. As an example, with my printer turned off, trying to discover the printer, the Printer Browser goes through its searching routine, but not finding any printer, before long the progress indicator stops and the "Add" button remains greyed out (not clickable), as does the "Print Using:" selector. From what you describe, it appears that it just can't find a driver.
In that "Print Using:" selector, can you choose "HP" and then see a long list of printer models, just not specifically your model? If so, that would indicate that the HP drivers were installed as part of your OS X.
What I would do is download and then install the 10.4.9 Combo Update over top of your current OS 10.4.9 in the hopes that it can replace or put back in place whatever is missing or necessary. Mine is up-to-date and working, and in that list I can't find either my printer or yours, so I'm not particularly concerned about that. The proof is not whether it can be "seen" by us, but whether or not it can be discovered and applied by Bonjour.
Let us know if the Combo Update is an effective solution or not. In the meantime, I'll look into another possibility I have in mind.