Hi Collin,
I've also been intrigued by this question for a long time. There was a speaker at a Guild conference many years ago who had done extensive research on the subject. I don't remember her name or affiliation, I think she was a scholar of sorts. She showed slides of the roof system in a building she dated to AD 500-something, on the Sinai Peninsula as I recall, and associated with a monastery, with masonry walls. It appeared to be a well-engineered truss, not at all basic or experimental looking. I wonder if Joel, Will, or another long-timer could back that up?
I've also seen in print the claim that remains of buildings preserved in peat-bogs in England or Ireland dating to about 4000 BC contain mortice and tenon joints. Sorry I can't give you the source [not because I'd have to kill you then, but I don't remember].
As I walked through a gallery in the Hermitage Museum in St. Petersburg, Russia years ago, dazed by the enormous variety of Old Master artwork, suddenly a painting jumped off the wall at me. It showed Jesus and Joseph, his father, busily working on a large timber on horses. I think it dated to the 1400's. Sorta ran a chill up my spine.
Leon