This is indeed a frustrating issue.
If the xbox app network status shows connected or up for all settings and NAT type says open, then you are mostly there.
I additionally had to turn on windows firewall, as I normally only use my router firewall.
Check these ports on your router, but don’t trust me, go look at xbox games for windows, or windows store games and you will see these ports listed:
XBLive
- Port 53 (UDP and TCP)
- Port 80 (TCP)
- Port 88 (UDP)
- Port 500 (UDP)
- Port 3074 (UDP and TCP)
- Port 3544 (UDP)
- Port 4500 (UDP)
PLUS add the port for teredo, although normally that changes from reboot to reboot, but not always.
Let me know if this helped you at all.
I should mention, when connecting to another players group, that from time to time they disappear, just to come back 30 seconds later.
I have not found the cause of this occurring yet.