Just to add another's voice, really, really liked this story. I've been having trouble with some of Podcastle's entries as of late, due to a tendency towards slower delivery leaving me a little frustrated and bored, but here I thought the tempo was just right. The delivery was slow, but the situation and especially the perspective of the speaker so interesting that my mind didn't wander a bit. I especially love the use of a reliable, but ultimately unsympathetic narrator (until his turn at the end). I caught on immediately that he was intended to be rather unsympathetic and skeezy due to the incessant use of titles and overly formal language in addressing the letter's recipient, making me feel he was a rather obsequious cog in a ponderous oppressive mechanism. Oddly, I found him much more interesting than the Red Priest himself, as the priest went through all these events essentially unchanged, something of an omniscient action hero in his own world. The speaker, by contrast, reverses completely in the course of the story, and I would much more like to hear more stories of that character, exploring his world with new eyes. I am, however, completely unfamiliar with the Red Priest character or his world, so I may be missing some aspects of his character. The particular events which brought him his outlaw status could be very interesting.
My only problem with the story also arose from my unfamiliarity with the setting: I was convinced initially that we were living in a high-fantasy world with it's own unique religions and unique church structure. The reveal that this was supposed to be a particular historical era in our world (i.e., the religion was Catholicism and the recipient of the letter the Pope) took me a few minutes to adjust to.