VoIP Phones not working inside LAN

I have tried to read many documents on running a VoIP system behind a NAT'd router, going out to the Internet, then back through a dedicated connection for the VoIP server. I am not getting anywhere with my research.

I inherited a setup where all the VoIP server equipment is on its own network, with a dedicated ADSL connection. Phones from anywhere on the Internet work! My problem is, from inside my network.

I have tried the usual troubleshooting steps: rebooting the router, disabling the firewall, changing the ports I plug the IP Phones into, but none of this is working.

We use Linux servers as our routers, and iptables as our firewall. The default policies are to DROP packets that do not match, but the issue persists even when I tell them to ACCEPT. Running a tcpdump -ni eth1 host 192.168.0.89 outputs the following as the phone is trying to connect:

tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth1, link-type EN10MB (Ethernet), capture size 65535 bytes
13:45:24.487637 ARP, Request who-has 192.168.0.89 tell 192.168.0.89, length 46
13:45:33.285767 ARP, Request who-has 192.168.0.89 tell 192.168.0.89, length 46
13:45:43.333432 ARP, Request who-has 192.168.0.89 tell 0.0.0.0, length 46
13:45:49.331224 ARP, Reply 192.168.0.89 is-at 00:15:b7:48:04:cd, length 46
13:45:49.337216 ARP, Request who-has 192.168.0.89 tell 192.168.0.89, length 46
13:45:49.341575 ARP, Request who-has 192.168.0.89 tell 192.168.0.89, length 46
13:45:49.444252 ARP, Request who-has 192.168.0.89 tell 192.168.0.89, length 46
13:45:49.612308 ARP, Request who-has 192.168.0.3 tell 192.168.0.89, length 46
13:45:49.612319 ARP, Reply 192.168.0.3 is-at 00:22:b0:70:9a:eb, length 28
13:45:49.613504 IP 192.168.0.89.50138 > xxx.xxx.xxx.xxx.1719: UDP, length 125
13:45:49.631597 IP xxx.xxx.xxx.xxx > 192.168.0.89: ICMP host 216.57.190.87 unreachable - admin prohibited filter, length 36

The xxx.xxx.xxx.xxx is the VoIP Server's public IP address (different ISP from our main network). If I skip my server and plug a phone directly into our Internet connection (we have a /24 subnet), it connects very quickly. If it's behind any of our servers, it will stop at that part of the handshake. I have tried on different gateways, same effect.

From inside my network, I can RDP into the management system, ping the server, etc. I just cannot get my phones to connect. When I dump my iptables out, so everything is set to ACCEPT, it still does not connect.

Where can I look next to get these phones working? They used to work, but they do not anymore; going back to that old configuration is not possible, as the backups are only around for 3 months.