This isn't an answer, this is more information as I have access to the servers Jono's describing.
We currently have the problem as described on one box. E.g., trying to do a curl google.com times-out, SMTP out is not happening, but I can SSH in, and Apache is serving web pages with no problem.
If I disable the firewall with sudo ipfw disable firewall, outgoing traffic resumes. If I then re-enable the firewall with sudo ipfw enable firewall, the problem reappears.
I'll enclose the firewall rules. Any suggestions?
$ sudo ipfw show
00001 1123672 159015812 allow udp from any 626 to any dst-port 626
01000 70125526 26073450472 allow ip from any to any via lo0
01010 0 0 deny ip from any to 127.0.0.0/8
01020 0 0 deny ip from 224.0.0.0/4 to any in
01030 0 0 deny tcp from any to 224.0.0.0/4 in
12301 904047 139023698 allow tcp from any to any out
12302 63538 11694670 allow tcp from any to any dst-port 22
12302 0 0 allow udp from any to any dst-port 22
12303 304700 44969494 allow udp from any to any out keep-state
12304 0 0 allow tcp from any to any dst-port 53 out keep-state
12304 0 0 allow udp from any to any dst-port 53 out keep-state
12304 0 0 allow tcp from any to any dst-port 53 out keep-state
12306 171 10944 allow tcp from any to any dst-port 311
12307 2167 143175 allow udp from any to any dst-port 626
12308 1604 98058 allow icmp from any to any icmptypes 8
12309 1604 98058 allow icmp from any to any icmptypes 0
12311 228466 17139842 allow tcp from any to any dst-port 80
12312 3349 616527 allow tcp from any to any dst-port 443
12313 386 18279 allow tcp from any to any dst-port 3283,5900
12313 4 130 allow udp from any to any dst-port 3283,5900
65534 885514 49998498 deny ip from any to any
65535 0 0 allow ip from any to any