I have exactly the same problem, but with a Linksys WRT3200ACM as my NAT at one end, where I have set up port 51830 forwarding, but a Cafe WiFi NAT at the other end which I don’t control.
My Linksys does not have a static IP, but it does have dynamic IP. (And the IP hasn’t changed in years anyway.)
Thanks,
Philip