This is what is happening:
--@--:~$ telnet [removed] 587
Trying [removed]...
Connected to [removed].
Escape character is '^]'.
220 [removed] ESMTP Postfix (Ubuntu)
mail from:fultron
250 2.1.0 Ok
rcpt to:someaddr@gmail.com
554 5.7.1 <someaddr@gmail.com>: Relay access denied

My question is this: how do I configure postfix in a way that I can send email to any email address I recognize the security implications of this, and I am planning on adding authentication after I figure out how to solve this problem.

A Note: I've done a substantial amount of google'ing -- most posts discuss how to allow relaying to one specific server, or a whitelist. I would like to be able to relay to any server. In fact, after reading some of the posts, I'm not even sure relaying is really what I want to do -- but I could be wrong.

Another Note: I need to be able to do this from outside of the local network.

My current main.cf file, comments stripped:
smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu)
biff = no
append_dot_mydomain = no
myhostname = [removed]
home_mailbox = Maildir/
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
myorigin = /etc/mailname
mydestination = [removed - this is the domain], localhost
mynetworks = 127.0.0.0/8
mailbox_command = procmail -a "$EXTENSION" DEFAULT=$HOME/Maildir/ MAILDIR=$HOME/Maildir
mailbox_size_limit = 0
recipient_delimiter = +
inet_interfaces = all

I tried adding a wild card to mynetworks and mydestination, to no avail.

Any help would be greatly appreciated.

After a day of hacking, I finally got a fix. Here is the new main.cf file (comments stripped,) for anyone struggling with this. It is important to note that I used SASL/TLS for authentication -- you will probably have to do the same. There are some good guides out there, especially if you're using Ubuntu.

smtpd_banner = $myhostname ESMTP $mail_name
biff = no

append_dot_mydomain = no

readme_directory = no

smtpd_tls_cert_file = /etc/ssl/certs/smtpd.crt
smtpd_tls_key_file = /etc/ssl/private/smtpd.key
smtpd_use_tls = yes
smtpd_tls_session_cache_database = btree:${data_directory}/smtpd_scache
smtp_tls_session_cache_database = btree:${data_directory}/smtp_scache

myhostname = [your hostname]
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
myorigin = /etc/mailname
mydestination = [your hostname], localhost
relayhost =
mynetworks = 127.0.0.0/8
mailbox_size_limit = 0
recipient_delimiter = +

inet_interfaces = all
inet_protocols = all

home_mailbox = Maildir/
mailbox_command = procmail -a "$EXTENSION" DEFAULT=$HOME/Maildir/ MAILDIR=$HOME/Maildir

smtpd_sasl_local_domain =
smtpd_sasl_auth_enable = yes
smtpd_sasl_security_options = noanonymous
broken_sasl_auth_clients = yes
smtpd_recipient_restrictions = permit_sasl_authenticated,permit_mynetworks,reject_unauth_destination
smtp_tls_security_level = may
smtpd_tls_security_level = may
smtpd_tls_auth_only = no
smtp_tls_note_starttls_offer = yes
smtpd_tls_CAfile = /etc/ssl/certs/cacert.pem
smtpd_tls_loglevel = 1
smtpd_tls_received_header = yes
smtpd_tls_session_cache_timeout = 3600s
tls_random_source = dev:/dev/urandom
smtp_use_tls = yes


The user will have to authenticate (see sasl and saslpasswd) before sending to email addresses that are not local.