In your router, enable “IGMP Snooping”, particularly if one of the affected machines is connected via wireless.
Minecraft uses IGMPv2 multicast to tell other computers on the network that it’s hosting a server. In my router, it was in the “Professional” tab of the “Wireless” configs page.
Enable configurations named something like “IGMP Snooping”, “Multicast”, “IGMPv2”. That’s your foot in the door to solving what I’m sure is a most frustrating problem 😉
Some more info: https://superuser.com/questions/1117756/how-does-minecraft-find-lan-servers