Funnily enough, I think this is because in Medieval times the most common state for traders and merchants was to be mobile and traveling. It was only the guys selling stuff to universities (like the medieval equivalents of ink, pens, paper, envelopes) who had such a valuable and regular customer that they could afford to set up a station[ae]ry shop!

Now I write it out sounds unbelievable, and I can't think of a reputable source, but I've been telling this story for years.

Does this make a mailed letter “nonstationary stationery”?

Oh thanks for the heads up, never knew that. Now to fix all the places I misspelled it...