Nessus when?
I think I've made it through all the archives now, having at last finished IGJ (and recovered from my amazement at how good it is), and I can't believe no one has mentioned this solution of how Horn, 300-some-years travel from the Urth of Typhon's time could return and find himself in the much-later time of Severian.
Time dialation. The trip took 300-some years in the Whorl's reference frame and thousands of years from Urth's reference frame.
-Rostrum
*This is WHORL, for discussion of Gene Wolfe's Book of the Long Sun.