It's possible to publish your public PGP key in the DNS. There is a really good guide at http://www.gushi.org/make-dns-cert/HOWTO.html
which explains the three different methods in detail. It's really simple though, so I'll explain how I did it. I'm going to replace my email address with a fake address to avoid feeding the spambots.