The closest natural experiment we can make is to expose an untrained contemporary French speaker to a reading of a text from that period. Conveniently, the poems of Chrétien de Troyes are only a few decades older. I consider myself a relatively educated native speaker of French with basic (but not extensive) training in the relevant fields, and I must say that even taking into account that poetry is presumably harder than ordinary speech, I find a passage such as
Mere, ne soliez vos dire
que li enge Deu nostre sire
sont si tres bel c'onques Nature
ne fist si bele criature,
n'el monde n'a si bele rien ?
- Biax filz, ancor le di ge bien.
Jel dis por voir et di ancores.
- Teisiez, mere ! Ne vi ge ores
les plus beles choses qui sont,
qui par la Gaste Forest vont ?
Il sont plus bel, si con ge cuit,
que Dex ne que si enge tuit. »
La mere antre ses braz le prant
et dit : « Biax filz, a Deu te rant,
que mout ai grant peor de toi.
Tu as veü, si con je croi,
les enges don la gent se plaignent,
qui ocïent quanqu'il ataignent.
- Voir non ai, mere, non ai, non !
Chevalier dïent qu'il ont non. »
extremely hard to understand (and yet it is so famous that I knew most of the exchange beforehand), and in particular much harder to understand than anything Les Visiteurs say in the film (but who doubted that about a comedy marketed at families?). That said, I do understand most of it and many French can read these texts fluently. More generally, I find that the main difficulty I encounter when reading texts from that period is that I don't know the exact meaning of a couple of grammatical words or constructions (so that I'm not quite sure whether the sentence is, for instance, hypothetical or assertive). The syntax is very odd but completely understandable and the vocabulary is a mixed bag, with the overwhelming majority of the words at least ringing a bell, but with a fair number of them having manifestly a slightly different meaning that the one I am used to.
Based on this, I would say that an educated native speaker of French would probably require only a few days of training to be able to follow a conversation in XIIth century French, but that the first encounter would probably be quite puzzling.
UPDATE: So, there is a very easy to find out. I asked a friend with a PhD in Old French to read once the text above at normal delivery speed to a group of twelve students (age 18 and 19) with no prior knowledge of Old French (a few of them even wondered afterwards what the language was, but a few others volunteered that it was a tale of knighthood in Old French), nor in fact of Medieval literature (as evidenced by the fact that none recognized the text even after I provided the translation, even though it is a relatively famous scene from the most famous work of Chrétien de Troyes). They were allowed to share what they had understood afterward. This is what they got.
This is a dialogue between a son and her mother. The son has seen or wants to see beautiful things in a forest. The mother also knows about them and maybe wants to see them. The mother is afraid for her son. Perhaps the son wants to be a knight.
This has to be compared with the original (my translation, deliberately as close to the original text as can be).
Mother, didn't you tell me that the angels of God our lord are so beautiful that Nature never made creatures so fair and that there is nothing so beautiful in the world? Beautiful son, and so I say again. I said it once and then again. Silence, mother! Didn't I just see the most beautiful things that may be, going through the Waste Forest? The mother, taking him in her arms, says Beautiful son, may God keep you, for I have great fear for you. You have seen, or so I believe, the angels about whom everybody complains and who kill what they touch. Not at all, mother, no! Knight is their name, they said.
Compared with the original, I was surprised that none mentioned either God or angels in their summary and interested by the fact that they, like me, find it especially hard to identify mood and modality (about half thought the son wanted to go in the forest see the beautiful things and the other half thought, correctly, that he had already seen them in the forest).