Parece ser que el texto más antiguo conocido en lengua castellana son las Glosas emilianenses, una serie de anotaciones de los siglos X y XI escritas en castellano y vasco al margen de un texto en latín. Aquí hay un fragmento, cortesía de Wikisource:

Suponiendo que la persona con la que te encuentres hable un registro similar al de nuestro monje, con un poco de esfuerzo y tras acostumbrarse a sus particularidades habría que ver si la comunicación es posible. También ayuda que se conozcan otros idiomas romances peninsulares como el portugués, gallego, catalán o asturiano, o extrapeninsulares como el italiano o rumano, para rellenar los huecos que el castellano no cubra.
Ahora, hay algunas controversias acerca de si las Glosas emilianenses fueron realmente escritas en castellano o algún dialecto hispánico. Aquí hay un texto que es más claramente castellano, aunque dos siglos posterior:
- Sj alguna christiana fiziere fornjçio con judio o con moro o con omne de otra ley, seyendo fallados en el fecho, o si les fuere sabido por pesquisa derecha, amos ssean quemados.
- Sj alguno que fuere sieruo de otro casare con la mugier daquel cuyo sieruo fue, amos mueran por ello, tan bien ella commo el.
- Sj alguna mugier prennada, por qual culpa quier que ffaga fuere judgada amuerte o a pena del cuerpo, non ssea justiçiada njn aya pena ninguna en su [f. 92v] cuerpo fasta que sea parida. Mas si debda alguna deuiere & non ouier de que la pagar, rrecabdenla por prision o por otra guisa, sin pena de su cuerpo, fasta que pague la debda.
Anónimo (c 1196). Fuero de Soria.
Este se entiende un poco mejor, pero habría que ver si la pronunciación permitiría la comprensión. Yo entiendo el portugués escrito, pero no el portugués hablado; y algo similar me ocurre con el francés. Que entienda el contenido del texto no significa necesariamente que sea capaz de mantener una conversación hablada en el castellano de la misma época.
Veamos algunos otros textos:
"Las partidas deuen prometer la una a la otra la pena que es en el conpromisso puesta, et si aqueilla pena fuere prometida al árbitro, tenido es el árbitro, et ante la pena dada, et depués, a cada una de las partidas contra la otra, de leixar el pleito quoando quiere que aqueilla partida lo demandare, (17) sobre esto ni aqueill árbitro aurá algo d'aqueilla pena, ante, si demandare la pena o partida d'aqueilla pena d'aqueilla partida que non quiere obedir en iuditio ho fuera de iuditio, deue dar todo aqueillo que demandare a la partida que quiere obedir."
Anónimo (c 1250). Vidal Mayor.
"Sigujent mjentre es a dezir de los sortores. Mando encara que, si algún sortor de las cosas que le fueren dadas a obrar cameará o furtará et prouado'l fuere, péchelo asín como ladrón; si non, jure solo, si le oujere sospecha, et sea credido. Que algunos d'ellos suelen a las deuegadas alguna cosa de los pannyos furtar o de las pielles o de la orla. Mas si el sennor de la obra o de las uesteduras prouar non lo pudiere et el dannyo fuere de V sueldos asuso, el sortor sáluese así como de furto, segunt razón del dannyo; de V sueldos ayuso, así como es dicho, jure solo."
Anónimo (c 1300). Fuero de Teruel.
"Estando este Çid Ruy Díaz en la su çibdad de Valençia, el grand soldán de Persia, porque oyera dezir de las grandes vondades d'él en el fecho de las armas qu'el Çid fazía e cómo nunca fuera vençido de moros ni de cristianos e cómo ganara la çibdad de Valençia e otros muchos castillos, ovo sabor de ser su amigo e enbió a él un cavallero mucho onrado, que era su pariente, con muchos nobles dones, con sus cartas de muchas palabras amigables e de grande amor. E como el Çid sopo su venida, saliólo a reçebir con toda su gente noblemente vestidos, e sus cavallos e armas con sus pajes a par de sí, que eran más de mil D cavalleros, a una legua de Valençia, que encontraron aquel moro con su noble conpañía."
García de Salazar, Lope (1471 - 1476). Istoria de las bienandanzas e fortunas.
"Si dizes que para acordarte de Dios no has menester ymagines, es verdad, y no te las dan para esso, sino para que te mueba a effectos la representazion de la deydad que reuerenziamos y del Señor que amamos sobre todo bien; como los enamorados, que el retrato de su dama no le trahen para acordarse de ella, pues ya presume memoria el acordarse que le trae para sacarle: trahelo sòlo para deleytarse con la parte que se le conçede del bien ausente. Dizes tanbien que Cristo pagò por todos, y que no ay sino viuir como quisieremos, porque el que me hizo a mì sin mì, me saluarà a mì sin mì. Bien que me hizo sin mì, pero hecho, siente que se destruya su hobra, manche su pintura y vorre su ymagen."
Quevedo y Villegas, Francisco de (1608). Sueño del Infierno.
La facilidad para comprender el texto aumenta, evidentemente, según las fechas se van acercando a la actual. Yo personalmente considero que el castellano del siglo XVIII, tomando solo los documentos escritos, es prácticamente indistinguible del español actual, o no se distingue del mismo más que, por ejemplo, algún dialecto hispanoamericano. Hasta entonces, la evolución del castellano se ha dado en un proceso gradual, por lo que a partir de cuándo se empieza a comprender es difícil de decir, y (pura especulación) tendría que ser en algún momento entre el siglo X y el XV.
Existe, en realidad, un texto aún más antiguo al de las Glosas: los Cartularios de Valpuesta, del siglo IX. He aquí un fragmento del año 844 con su traducción (más ejemplos en el enlace):
"...in loco que uocitant Elzeto cum fueros de totas nostras absque aliquis uis causa, id est, de illa costegera de Valle Conposita usque ad illa uinea de Ual Sorazanes et deinde ad illo plano de Elzeto et ad Sancta Maria de Uallelio usque ad illa senra de Pobalias (...), posuimus inter nos fuero que nos fratres poniamus custodiero de Sancta Maria de Valle Conpossita..."
"...en el lugar que llaman Elicedo con fueros de todas las nuestras excepto alguna causa de fuerza, esto es, de la costera de Valpuesta hasta la viña de Val Sorazanes y de allí al llano de Elicedo y a Santa María de Vallejo hasta la sierra de Pobalias (...), hemos puesto entre nosotros fuero que nosotros hermanos pongamos guardián de Santa María de Valpuesta..."
El enlace explica algunos cambios, tanto gráficos y fonéticos (f > h, x > ç, u > o, etc.) como sintácticos (se abandonan los casos latinos, se favorece la estructura sujeto-verbo-complementos, plural con "s", etc.), que alejan al texto del latín y lo acercan al castellano. Basándose en los textos presentados, es un tanto optimista pensar que pueda haber comunicación entre un hispanoparlante del siglo IX y uno moderno. Es igualmente difícil en el año 1000 (Glosas emilianas), y parece que se vuelve algo más sencillo hacia el 1200 (Fuero de Soria). Si tuviera que aventurar un número, apostaría por el siglo XIII.
NOTA: Todos los textos se han extraído del CORDE, un corpus de textos en castellano digitalizados, con los posibles errores de digitalización de todo OCR.