Figured out that if I forward all udp packets for the whole ephemeral range (default is 32768 to 60999 for most Linux boxes) on the router, NAT type becomes unrestricted and the proxy starts to get SDP offers at a much faster rate.
Still have some questions with iptables setting, will start a new topic for it.