Postfix: set up outgoing server to server encryption

I'm trying to configure postfix that it sends a mail encrypted with TLS to the recipient server.

What I have: receiving mails encrypted (other server -> my server) and users can connect encrypted to my server.

Server: Debian 7.2 with postfix 2.9.6

config lines:

/etc/postfix/main.conf (relevant codelines)

smtp_tls_security_level = may
smtp_use_tls = yes
smtp_tls_policy_maps = hash:/etc/postfix/tls_policy

/etc/postfix/tls_policy (just for testing, I want it for all domains)

google.com encrypt
.google.com encrypt
gmail.com encrypt
.gmail.com encrypt

I tried some combinations of the above and even put it directly in the master.conf, but nothing works:

Dec 10 10:10:21 myserver postfix/smtp[7101]: 9019B4583500: to=<[email protected]>, relay=gmail-smtp-in.l.google.com[173.194.70.26]:25, delay=0.96, delays=0.13/0.01/0.27/0.55, dsn=2.0.0, status=sent (250 2.0.0 OK 1386666621 u49si13392861eep.148 - gsmtp)

What am I doing wrong?

You must set smtp_tls_security_level to a value other than none or may (what you have now).

Note that there are a lot of other factors playing into this, and you may need to set other values as well. See postfix' TLS README.