All you need for discovery is broadcast access, and TCP/IP grants that. The discoverer broadcasts, "I'm looking for devices!" And the discoveree replies "Here I am!" Boom, connection is made. This is how game server browsers worked for LAN play back in the day.

Is it really so inconceivable that a phone is connected to a wi-fi gateway on a regular LAN?

Because that is how my network is set up here at home.