http://www.illuminatedcomputing.com/posts/2013/07/public-key...
http://www.illuminatedcomputing.com/posts/2013/07/public-key...
Also, I don't think there's a problem around the fact that most of the time you don't communicate directly with the recipient's smtp server - relaying is definitely a part of SMTP. It would work in the case of running your own SMTP server that you use to relay mail (assuming you encrypt your own SMTP sessions), but you'd need smtp servers to recursively query for the public key if you want to enable relaying.
This is starting to sound suspiciously like DNS, so why not just store the keys there? There are already ways to do that:
http://www.gushi.org/make-dns-cert/HOWTO.html
Add in DNSSEC records and you can be pretty certain you have the right key.
X-Purrcat-Key: ...public key goes here....TL;DR: just make your header Purrcat-Key.