The HPLIP package contains a custom implementation of mDNS queries (actually, 2: one in the core C code and one in python for the administration tools). This implementation is simplistic and sub-optimal. I fixed a problem of this implementation in the past, but unfortunately my patches don't apply on the latest HPLIP releases, and aren't easily forward-ported.

The Right Thing to do for mDNS on Linux use use avahi calls. I want to look into using avahi for this purpose in HPLIP.

I have one problem: the Envy 5530 printer with which I was having the mDNS problems is broken. I have a new one which isn't using mDNS. So I can't test the stuff here any more. If anyone has an Envy printer connected via WLAN, testing would be very welcome.