It's not exactly at the same period, but to give you a picture in the Viking Age at the beginning of the medieval period, the vikings were trading with Constantinople (and I mean a big trade route), and sometimes with Spain and Italy. They also had spies in about all the royal court of the major countries of Europe and again in Constantinople. So yeah, people managed to communicate.

Plus, you must not forget that people at the time had slaves. So one might capture someone and sell him to, let's say an intellectual, looking to learn the language.