So to clarify:
Client -> Internet -> NAT -> FS
works
Client -> NAT -> Internet -> NAT -> FS
does not?
Since the FS NAT side appears to be working (from the 1st case), I'm guessing it's probably either a problem at the client side (with client or NAT router) or perhaps the double-NAT is causing an issue. Personally I haven't run FS behind NAT, so it's not a situation I've had to handle.
Do a packet trace of a call at both the client and FS ends. The FS end is easy - "sofia global siptrace on if you have low volumes, or a tool like tcpdump/ngrep if you have higher volumes. FS will actually log the SDP information in at debug-level console logs and in XML CDRs. At the client side try using Wireshark on the client PC.
Compare the SDP information of the call, to check the IP and ports seen at either end. Check whether they look reasonable. FS will need to see the public IP of the client, and the client see the public IP of FS for audio to work in both directions. The FS/client may not need to know their public IP on the internal side of the router as many routers have SIP ALG that will rewrite the internal IP to an external one, but if the client has already done so that often causes more problems than it solves.
FS can handle only knowing the internal IP of the client if they're able to send RTP to FS - it will see the IP/port the audio is coming from and send audio back to that address. That does mean audio won't work on such a call until it has received RTP from the client though.
-Steve