Well as far as I see in the written record, Old English and Old Norse were far from mutually intelligible, we have a fairly robust grammar of Old Norse and Old English to support this. There might well be a degree of crossover in the lexicon with elements of the vocabulary but from what I've seen of both the languages the pronunciation and grammatical elements differ enough that complete mutual intelligibility is unlikely.

However the impact of the written record does not preclude the possibility of a rather different situation in the speech of everyday speakers, I can think of a few scholars who argue in this vein including Eyþórsson (2002) and Matthew Townend (2000, 2002). Ultimately though I think these arguments are a bit vague and argue primarily based on the evidence of a swift integration of loanwords from contact with Scandinavian peoples.

Additionally the fact that the two languages are from different branches of the Germanic language family any natural mutual intelligibility is unlikely. This leaves any element of shared expression by the languages down to contact and diffusion, a mechanism woefully lacking in understanding in historical linguistics and in need of a lot of work to help facilitate its use in good historical analysis.

As such communication with all your mentioned speech communities would have been similarly difficult. Any first contact communication would have to rely on shared languages based on contact, either with each other or with other neighboring peoples. I imagine most of the communication was done through the scant amounts of their respective languages they shared and eventually by interpreters and second language learners. I have a feeling there was prior contact between elements of both societies with monks having some knowledge of ON, but someone would definitely have to confirm this.

Source: Studying for an MA in Linguistics Edit: I'm tired and this is poorly written.