Postfix smtp mail to external hosts not possible

I administer a server (Ubuntu 12.04 LTS) running a web server and a mail server – The web server is running all fine, but the mail server is a problem.
I have Dovecot installed and configured correctly – i can connect to it with Thunderbird (my client is in another network, so it is no internal network) and see all folders etc.
Mail from external is also received.

Postfix smtp authentication seems to work (using STARTTLS), as i can write emails from Thunderbird in external network to localhost and the domain of the server. But when I try to send an email to another address, for example to gmail, i get the following error:

An error occurred while sending mail. The mail server responded:  5.7.1 <***@gmail.com>:
Relay access denied. Please check the message recipient ***@gmail.com and try again.

I use a smtp relay on the postfix itself, when i log in with ssh I can write emails. I think the problem is somewhere here – does smtp connections to postfix also use this configured relay?

Here is my main.cf: (hostnames, domains etc. replaced by fictional data)

# See /usr/share/postfix/main.cf.dist for a commented, more complete version
# Debian specific:  Specifying a file name will cause the first
# line of that file to be used as the name.  The Debian default
# is /etc/mailname.
#myorigin = /etc/mailname

smtpd_banner = $myhostname ESMTP $mail_name (Ubuntu)
biff = no

# appending .domain is the MUA's job.
append_dot_mydomain = no

# Uncomment the next line to generate "delayed mail" warnings
#delay_warning_time = 4h

readme_directory = no

# TLS parameters
smtpd_tls_cert_file=/etc/ssl/certs/ssl-cert-snakeoil.pem
smtpd_tls_key_file=/etc/ssl/private/ssl-cert-snakeoil.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

# See /usr/share/doc/postfix/TLS_README.gz in the postfix-doc package for
# information on enabling SSL in the smtp client.

myhostname = mydomain.com
alias_maps = hash:/etc/aliases
alias_database = hash:/etc/aliases
myorigin = /etc/mailname
mydestination = mydomain.com, localhost, myhostname
relayhost = smtp.myrelayhoster.com
mynetworks = 127.0.0.0/8 [::ffff:127.0.0.0]/104 [::1]/128
mailbox_size_limit = 0
recipient_delimiter = +
inet_interfaces = all



smtp_sasl_auth_enable = yes
smtp_sasl_security_options = noplaintext noanonymous
smtp_sasl_password_maps = hash:/etc/postfix/sasl_password

sender_canonical_maps = hash:/etc/postfix/sender_canonical

As said, basic smtp auth seems to be working – does the relay need to be configured for smtp seperately?

These are the important lines of the /var/log/mail.log:

Sep  5 09:19:21 myhostname postfix/smtpd[9086]: connect from isp-ip.net[123.456.789.123]
Sep  5 09:19:22 myhostname postfix/smtpd[9086]: NOQUEUE: reject: RCPT from isp-ip.net[123.456.789.123]: 554 5.7.1 <example@gmail.com>: Relay access denied; from=<user@mydomain.com> to=<example@gmail.com> proto=ESMTP helo=<thunderbird>
Sep  5 09:19:22 myhostname postfix/smtpd[9086]: disconnect from isp-ip.net[123.456.789.123]