I would offer two unrelated suggestions:

1. The communicating processes should, as a matter of course, send everything through an encrypted channel.   This could be software-implemented (e.g. SSL), or it could be a known-good VPN-capable hardware router.   This precaution will serve to protect all of the communications between the two parties, whether the traffic consists of “secret messages” or just “protocol.”   (Remember that whatever system you choose must provide for, not only encryption, but identity verification and data integrity as well.)
2. Don’t bother to “roll your own” implementation when a standard implementation already exists:   namely, S/MIME.

What you really want is for the entire communication process to be as transparent as possible.   “You are stuffing e-mail messages through a secure channel.   The recipient, whether it is a Perl program or not, receives the messages as-tendered.   It Just Works.™”   Both parties know that the messages came from their stated senders and were received as-tendered, but, insofar as possible, do not have to be inconvenienced by the process of obtaining these assurances.   “Yeah, it’s robust and secure.   Big Deal.” = Perfect.