Let’s say for simplicity sake that there are exactly one of each type and that all three are using default OS settings.
Since Windows XP SP2, the built-in Windows host firewall has been enabled by default. That means Syncthing on Windows must generally initiate connections.
Android includes support for iptables in Linux, so depending on the particular Android version, it might also block inbound connections by default. Also, since Android 11, security changes have been affecting network discovery. Together it makes it more likely that Syncthing on Android will have to initiate connections.
For Linux, the default state of iptables (superseded by nftables in newer kernels) largely depends on the distro. Ubuntu and many other distros ship with no firewall rules by default while Fedora defaults to blocking all inbound connections except for DHCP and mDNS (plus port 22 for SSH on server editions). So odds are that Syncthing on a typical Linux system will accept inbound connections on port 22000 without user intervention.
This results in a situation where Syncthing on Linux “works fine” while on Windows there might be no connections, only via a relay, or intermittent – e.g., won’t connect to Android, but connects to Linux. Same for Syncthing on Android where it might connect to Linux but not Windows without going thru a relay.
With global discovery and relaying disabled, it increases the odds that some devices won’t automatically find its peers without manually setting local network addresse(s) for each device.
Depending on how much data changes at any given time, focusing on having Syncthing always using the mesh network might simplify your setup, i.e., use the mesh network even when all your devices are at home.
It takes time to find the right combination of settings to make it work seamlessly, especially for your particular setup which isn’t typical.
I’ve currently got five different VPNs configured on my primary laptop (including a mesh VPN), four PCs and five Android devices (phones and tablets) of varying vintages, all with Syncthing. My backup phone and tablet go months at a time without being powered on, but Syncthing finds a connection shortly after launching. Some devices have global discovery and relaying enabled, some do not (I’ve never seen any of my devices rely on a relay).