I have a similar problem where I can send/receive locally. I can receive mail from outside servers but not send out. I don't get problems with connection problems. I see in the in the email log that the email is being deferred because the host is not found. This sounds like a DNS problem to me but I am a newbie and am not sure of the changes to make in order to resolve the sending problem.

#cat /etc/hosts
# Do not remove the following line, or various programs
# that require network functionality will fail.
127.0.0.1 localhost.localdomain localhost
::1 localhost6.localdomain6 localhost6
204.14.162.232 mail.3coffice.com mail
#cat /etc/resolv.conf
search 3coffice.com
nameserver 209.218.130.4
nameserver 209.218.131.4
# host `hostname`
mail.3coffice.com is an alias for 3coffice.com.
3coffice.com has address 204.14.162.232
3coffice.com mail is handled by 10 mail.3coffice.com.
# dig 3coffice.com mx
; <<>> DiG 9.3.4-P1 <<>> 3coffice.com mx
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 59036
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 2, ADDITIONAL: 0

;; QUESTION SECTION:
;3coffice.com. IN MX

;; ANSWER SECTION:
3coffice.com. 2913 IN MX 10 mail.3coffice.com.

;; AUTHORITY SECTION:
3coffice.com. 2977 IN NS ns38.domaincontrol.com.
3coffice.com. 2977 IN NS ns37.domaincontrol.com.

;; Query time: 7 msec
;; SERVER: 209.218.130.4#53(209.218.130.4)
;; WHEN: Sat Jun 20 16:13:50 2009
;; MSG SIZE rcvd: 103
# dig 3coffice.com any
; <<>> DiG 9.3.4-P1 <<>> 3coffice.com any
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 61810
;; flags: qr rd ra; QUERY: 1, ANSWER: 4, AUTHORITY: 2, ADDITIONAL: 0

;; QUESTION SECTION:
;3coffice.com. IN ANY

;; ANSWER SECTION:
3coffice.com. 2925 IN A 204.14.162.232
3coffice.com. 2861 IN MX 10 mail.3coffice.com.
3coffice.com. 2925 IN NS ns38.domaincontrol.com.
3coffice.com. 2925 IN NS ns37.domaincontrol.com.

;; AUTHORITY SECTION:
3coffice.com. 2925 IN NS ns37.domaincontrol.com.
3coffice.com. 2925 IN NS ns38.domaincontrol.com.

;; Query time: 15 msec
;; SERVER: 209.218.130.4#53(209.218.130.4)
;; WHEN: Sat Jun 20 16:15:01 2009
;; MSG SIZE rcvd: 147