It seemed the firewall had something to do with it after all.
I turned it off again to test one more time, and in CUPS Web it picked up the same printer a third time, and in this new option (the middle one in "Discovered Network Printers") it just worked. As soon as I turn the firewall again the middle option disappears.
HP Device Manager still doesn't locate it but at least I'm able to use CUPS to print what I need.