It's released under the LGPL, according to its COPYING file, by HP. I am pretty sure that means the patent doesn't matter; HP is granting you a license to use it.
Strictly speaking the LGPL is a license that relates to copyright, not patenting. A separate patent license would also be required, unless you use a copyright license that also includes patent terms (I haven't reviewed LGPL in awhile to confirm, and obviously you need to specify about what exact version of LGPL you're referring to anyways).
Any GPL (any version) explicitly forbids distributing the software with external conditions restricting its ability to be redistributed. That puts it at odds with almost any conceivable patent license.
I think you're underestimating the creativity of patent lawyers a bit.
For instance, just off the top of my head, consider this: "OK, you can distribute the source all you want, but as soon as you compile it, you've created a patented product, the binary of which you can't distribute."
After all, the patent itself is supposed to give all the description one needs of how to implement the patented invention, it's when you fix the patent into something real that you violate the patent.
IMHO your mistaken about the second part. You can have a separate patent license. If the patent holder distributes software under the GPL, this would effectively license the patent for the related GPL work, or it wouldn't be correctly licensed under the standard GPL.
If a separate implementation is NOT a derived GPL work, then patent licensing may be a factor.(IANAL etc.)
Unfortunately, the copyright terms have nothing to do with whether you can actually use the algorithm/datastructure. It only means you can copy the source-code of a particular implementation of the algorithm/datastructure under the terms of the LGPL. If you want to actually run the code on a computer then you must contend with whatever enforcement or non-enforcement mechanism the author has in place for the patent.