I've already searched Wikipedia's list of time travel stories in hopes of finding it, but no such luck.
This is the basic plot of the story:
In the future, criminals are sent back to the Renaissance as this is considered a humane form of punishment. One man is wrongfully accused by one of his rivals/enemies and punished in this fashion. He resolves to take revenge on his opponent and writes a letter addressed to him. He passes the letter on to his descendants, along with information proving his innocence and the other man's guilt. In this letter he tells his opponent that he will be convicted and sent back in time just as the protagonist was, and that he will be waiting for him. He also tells him that he is certain his plan will work, because the man arrived just a few hours after the protagonist did, and that he killed him.
I remember this being a part of a collection of short stories. It's probably fairly old. Unfortunately, I don't remember much else about it.