OK, the Mac's mDNSResponder configuration was somehow messed up.
I could not see the Airport Extreme in the same subnet either.
So, when placed in the same subnet with the 255.255.0.0 net mask, I could add the printer using HP Utility, but not the HP configurator.
Now, this mac 'foo' can ping foo.local, but nslookup and dig cannot find foo.local
I then separated the subnets, and while I can access the printer by IP, I cannot print or use HP Utility. I guess because I cannot even ping printer.local
I enabled RIP v1 in the router and tweaked pf on the Mac with no success.
I want the printer in 2 VLANs which are otherwise disconnected. These are port-based VLANs, but they still require a separate subnet for each.
So I put the printer in its own VLAN, and made its port a member of the other 2.
But if I cannot get the printer name in .local, it's doomed.