The science bit:
smtp_use_tls = yes
# Send all mail through smtp.gmail.com
relayhost = smtp.gmail.com
# Stop getting a catpcha, hopefully.
smtp_destination_rate_delay = 60
relay_destination_rate_delay = 60
Now, edit /etc/postfix/sasl_passwd:
It doesn't have to be an @gmail account, it can be a GAFYD account, once you've logged into it once to activate it.
Then just generate the map file for the sasl_passwd file and reload. As root:
And you're done. Monitor your queue a few times over the first few days to make sure stupid stuff hasn't happened (the delay between mails might get tweaked), but in general this has worked for me.