HELP: At wit's end with Exim4, GMail and my corporate overlords

I now am at a loss at what to do. If you know something, please help.

I have Exim4 running as an MTA for a server that is inside a network run by paranoid network admins. There is a route-able IP which once incoming packets hit the gateway they get NAT'd to an RFC 1918 address on my box.

Exim4 can send SMTP traffic seemingly everywhere except google. The messages time out with google. That is, I am trying to establish an SMTP dialog with the servers in the MX records for gmail (and my google apps-hosted domains) and nothing happens:

-----

2008-07-18 14:24:30 1KJuTv-0001ca-Mq alt2.aspmx.l.google.com [209.85.147.114] Connection timed out
2008-07-18 14:24:39 1KJuX7-0001dS-9L alt2.gmail-smtp-in.l.google.com [209.85.147.27] Connection timed out
2008-07-18 14:26:55 1KJucM-0001dd-KV ASPMX.L.GOOGLE.COM [72.14.247.27] Connection timed out
2008-07-18 14:26:56 1KJucM-0001dd-KV gmail-smtp-in.l.google.com [72.14.247.27] Connection timed out
2008-07-18 14:26:56 1KJucM-0001dd-KV == treo@rdewald.com R=dnslookup T=remote_smtp defer (110): Connection timed out
2008-07-18 14:27:39 1KJuTv-0001ca-Mq alt2.aspmx.l.google.com [209.85.147.27] Connection timed out
2008-07-18 14:27:48 1KJuX7-0001dS-9L alt2.gmail-smtp-in.l.google.com [209.85.147.114] Connection timed out
2008-07-18 14:30:05 1KJucM-0001dd-KV alt2.gmail-smtp-in.l.google.com [209.85.147.27] Connection timed out
2008-07-18 14:30:48 1KJuTv-0001ca-Mq aspmx2.googlemail.com [209.85.135.27] Connection timed out
2008-07-18 14:30:57 1KJuX7-0001dS-9L alt1.gmail-smtp-in.l.google.com [209.85.129.27] Connection timed out
2008-07-18 14:33:14 1KJucM-0001dd-KV alt2.gmail-smtp-in.l.google.com [209.85.147.114] Connection timed out
2008-07-18 14:33:57 1KJuTv-0001ca-Mq aspmx3.googlemail.com [64.233.167.27] Connection timed out
2008-07-18 14:33:57 1KJuTv-0001ca-Mq == rdewald@hospicenyc.org R=dnslookup T=remote_smtp defer (110): Connection timed out
2008-07-18 14:34:06 1KJuX7-0001dS-9L gsmtp147.google.com [209.185.147.27] Connection timed out
2008-07-18 14:34:06 1KJuX7-0001dS-9L == rdewald@gmail.com R=dnslookup T=remote_smtp defer (110): Connection timed out
2008-07-18 14:36:23 1KJucM-0001dd-KV alt1.gmail-smtp-in.l.google.com [209.85.129.27] Connection timed out
2008-07-18 14:39:32 1KJucM-0001dd-KV gsmtp183.google.com [64.233.183.27] Connection timed out
2008-07-18 14:39:32 1KJucM-0001dd-KV == rdewald@gmail.com R=dnslookup T=remote_smtp defer (110): Connection timed out
2008-07-18 14:43:48 Start queue run: pid=6419
2008-07-18 14:43:49 1KJuX7-0001dS-9L == rdewald@gmail.com R=dnslookup T=remote_smtp defer (-53): retry time not reached for any host
2008-07-18 14:43:49 1KJucM-0001dd-KV == treo@rdewald.com R=dnslookup T=remote_smtp defer (-53): retry time not reached for any host
2008-07-18 14:43:49 1KJucM-0001dd-KV == rdewald@gmail.com R=dnslookup T=remote_smtp defer (-53): retry time not reached for any host
2008-07-18 14:43:49 1KJuTv-0001ca-Mq == rdewald@hospicenyc.org R=dnslookup T=remote_smtp defer (-53): retry time not reached for any host
2008-07-18 14:43:49 End queue run: pid=6419

----

Then it finally times out.

Googling about this gets me all kind of advice about how to use GMail as a smarthost.

I DO NOT EFFING WANT TO USE GOOGLE AS A SMARTHOST.

I just want to send SMTP traffic. Do they not accept any port 25 traffic at all? I can't believe that.