After many hours of debugging I may have a small lead.
I believe Zeroconf relies on multicast on both server and client sides. And from this older thread the app might not have permission to use multicast.
Not too sure. Because it looks like my code can discover some services (not the ones I want), but it's extremely hit/miss. Each 30s discovery will discover different services.