Double Nat is one of the worst things you can have when dealing with rtp. Also it depends a lot on the routers / firewalls you have.
The first thing I would try is set rtp_keepalive=1 at the endpoints as it sends rtp packets immediately and may helps to open the ports at the right time.
rtp_keepalive on endpoints didn’t work for me.
Only after 2 minutes I have audio stream.
I also added the invalid ip of gw that does the nat in media_address, however it doesn’t hear any changes in the SDP.
Would it be ideal to change this network to a network with a single NAT?
If you are able to change the network to single Nat, chances are high that it will work.
Another thing that I like to do in complicated Nat situations is to use VPN. You could install openvpn or zerotier on your vps and your clients and it will work like an ethernet cable without any Nat problems. Especially zerotier is set up in five minutes.
As a nice side effect you also add an extra layer of security since traffic is encrypted then.