Você e @joeqwerty tiveram uma discussão animada nos comentários para a pergunta e eu vou repetir algumas coisas.
Vamos começar de uma forma simples: existem vários protocolos padrão e vastos de protocolos proprietários de "autodescoberta" - isto é, protocolos pelos quais os hosts ou programas de cliente e servidor se localizam. Falar de "auto-descoberta" como se fosse uma entidade monolítica está contornando toda a questão. Tenha isso em mente por todo o tempo.
Você segmentou sua rede em várias LANs virtuais. As transmissões não serão comunicadas entre essas LANs virtuais. Muitos (a maioria?) Protocolos de detecção automática são baseados em broadcast, então eles não conseguirão localizar hosts em outras VLANs.
Conectar as redes juntas não irá ajudá-lo porque, na verdade, você fará todas as redes em uma grande LAN novamente. Todos os outros motivos que você tem para segmentar em várias VLANs estão fora da janela.
Encaminhar seletivamente protocolos entre VLANs é onde as coisas ficarão interessantes.
Protocolos padrão de descoberta automática baseados em IP, como NetBIOS "browsing", mDNS (conhecido como "ZeroConf" ou "Bonjour", e outros podem ser encaminhados entre sub-redes IP (que são tipicamente mapeadas de 1 para 1 para VLANs) por subinterfaces lógicas em roteadores) com software adequado de gateway de camada de aplicação.Existem vários produtos de vários fornecedores que podem fazer isso (use seu mecanismo de busca favorito e procure por "avanço rápido entre sub-redes" e você encontrará muitas coisas , por exemplo.
Protocolos proprietários de detecção automática serão mais problemáticos. Você terá que esperar que o software tenha sido escrito por alguém para encaminhá-los através de VLANs ou sub-redes. Os protocolos que funcionam apenas na camada 2 serão ainda mais problemáticos, pois, para lidar com as tabelas de adjacência, seus switches mantêm a contabilidade da VLAN com a qual um endereço MAC está associado. Qualquer software de gateway entre VLANs terá que ter algum tipo de funcionalidade proxy-MAC.
O que você está procurando não é impossível, mas terá que ser tratado em uma base de protocolo individual. Não há uma solução de "varinha mágica" que você possa aplicar para alcançar o resultado que está procurando.