I've written a STUN client that can send basic binding requests to stun servers and receive their replies. This works 100% of the time just fine.
My problems arise when I try to use the data returned to me to initiate a connection between two clients, both behind a NAT. At least one of them is behind a NAT where "Full-cone NAT" is enabled, to ensure the router will allow connections from a different IP than the STUN server to connect to the same port.
This works sometimes just perfectly on the first attempt I make, other times it works after having retried several times.
To try and find out why this might be, I started looking at the CHANGE-REQUEST, by attaching a CHANGE-REQUEST attachment to the binding request packet, after the initial normal binding request had been made. This had the same success rate as with my second client trying to establish a P2P connection. I noticed that as soon as the reply on the CHANGE-REQUEST from the second STUN server IP would arrive, the 2nd client would have no problems connecting either. (to be clear, the request is made to the same IP as the previous, but the response arrives from a different IP)
Is there anything that could explain why it works so randomly? I would expect it to either work or not, but not this random behavior. I doubt it's some sort of anti-flood protection from the router, as it often fails on the first few attempts and then randomly works for several attempts afterwards.