You didn't publish the results of your stunclient
run, but I imagine it looked something like the following:
$ stunclient --mode full --localport 9999 stun.stunprotocol.org
Binding test: success
Local address: 192.168.1.8:9999
Mapped address: 1.2.3.4:9999
Behavior test: success
Nat behavior: Endpoint Independent Mapping
Filtering test: success
Nat filtering: Address and Port Dependent Filtering
I'm going to guess that your Behavior Test is "Endpoint Independent" and the Filtering test was "Address and Port Dependent" as those are the most common in the home and mostly matches with what you described above. (aka as "port restricted NAT").
In any case, this means you have created a port mapping between yourself and the STUN server. In the example above, my public IP address is 1.2.3.4. And is common, but not always the case, my local port (9999) is the same as the public port.
Internally, your NAT keeps a logical table such as the following:
------------------------------------------------------------------------------------
|| LOCAL IP | LOCAL PORT || EXT PORT || REMOTE IP | REMOTE PORT ||
||================================================================================||
|| 192.168.1.8 | 9999 || 9999 || 107.23.150.92 | 3478 ||
------------------------------------------------------------------------------------
Because you sent out a packet from port 9999 to the stun server (107.23.150.92), the NAT creates a port mapping entry in it's table for several minutes. When a packet arrives on the NAT/router from the Internet, it consults the table. When the response came back from the STUN server's IP:port, the NAT was able to forward it to your computer behind the NAT based on the "remote" fields in the table above.
But there is no port mapping between you and the "other public machine" that you are hoping to receive data from. Let's assume that the IP address of that other machine is 2.4.6.8 and it is attempting to send from it's local port 8888. The NAT still doesn't have anything in the table to map traffic from 2.4.6.8:8888 to a host behind the NAT. So when traffic arrive at a NAT from an a host not in the table, the NAT only knows to drop the packet on the floor. There is a NAT classification known as "Cone NAT" where this would work, but those aren't as common.
In your case, there is an easy workaround. After obtaining a port mapping from the STUN server, send another datagram from your same local port (9999) to the remote host (and remote port) that you want to receive data from. The remote host can simply ignore this datagram, but it effectively creates another port mapping entry on your NAT
------------------------------------------------------------------------------------
|| LOCAL IP | LOCAL PORT || EXT PORT || REMOTE IP | REMOTE PORT ||
||================================================================================||
|| 192.168.1.8 | 9999 || 9999 || 107.23.150.92 | 3478 ||
|| 192.168.1.8 | 9999 || 9999 || 2.4.6.8 | 8888 ||
------------------------------------------------------------------------------------
That simple 1-byte data packet to 2.4.6.8:8888 allows the NAT to forward traffic back from that address to your host behind the NAT.
In other words, using your own network flow nomenclature:
My machine:9999 ---->[STUN BINDING REQUEST]--->stun server:3478
My machine:9999 <----[STUN BINDING RESPONSE mapped IP:port]<--- stun server:3478
My machine:9999 [Open socket on port 9999]
My machine:9999 ---->[1 byte datagram] -------> 'other:8888'
My machine:9999 <---- [UDP to public IP:port obtained in step 2]<----'other:8888'
Typically, in a normal P2P flow, both endpoints work with a STUN server to discover their port mapping. And then use another service on to exchange IP:port information between each other. From what you describe, you are manually exchanging these values between your programs, which is fine for testing.
If the other machine is on the public internet, you technically do not need STUN. The first machine (behind a NAT) can just send directly to the remote IP and port to say, "send me some data". The remote side just inspects the peer address and port of this message to decide where to send back to. The port mapping has already been created. Some RTSP clients assume the server is public
My answer on the basics of socket NAT traversal is here.
I happen to know the developer of STUNTMAN. He's a reasonably nice guy, good looking, and very smart. They also say him and I look alike and have near identical spelling with our names. You can always mail him directly if you have questions about STUN and NAT traversal.