Most of the time I use public networks at my campus where it's not possible to forward a port. However, I have set up a VPS with a public IP and I have OpenVPN running on it. Using firewalld and masquerade I have set up my own PC to route all traffic via the server, and it works. I have also set up the 6112/udp port on the server's public address to be forwarded to my machine's internal VPN address, and ensured there were no local firewalls preventing incoming connections. I tested this using the ncat utility and had successfully received and sent UDP packets on my local machine port 6112 from and to a third party server. UPnP is disabled in client settings, as my VPS doesn't support it.
HOWEVER, each time I join a lobby, there're always 1-3 people on the list I can't connect to. It just says "Connecting to ***..." forever. ReFAFing doesn't seem to work for neither me nor them. I have tried switching to the port 7712/udp and still had no luck. I always get kicked and that really annoys me.
Attached are the logs which contain records for my last few attempts to play a game. It can be seen that connection state is PUBLIC in all cases. I would like to hear some suggestions on what could possibly go wrong in such a scenario. I can probably fix the problems myself, I just want them pointed out, as I don't know all the technical details of how FAF connects to other players.