Proto-Germanic ancestor of meðan
According to my source (Ásgeir Blöndal Magnússon: Íslensk orðsifjabók, 1989), (á) meðan (“while, meanwhile”) comes from (the ancestor of) með (“with”), *þa-n-, instrumental of *sa, and a particle *ī. Cognates are, among others, Swedish medan, emedan (Old Swedish mæþan, emæþan, æmæþan), Danish medens, imedens, mens, imens (Old Danish (e) mæthæn, j mæþæn), Faroese meðan, meðani, Gothic 𐌼𐌹𐌸𐌸𐌰𐌽𐌴𐌹 (miþþanei), Old English mid þon þe. The *-ī seems to be primarily based on Gothic, but might be considered supported by Faroese. I don’t know what this particle or suffix represents. SAOB posits a form miþþanī; do you find this plausible? Should we perhaps rather split the words, as in Old English? What would it then be? Perhaps *midi þan(ō) ī?
Hmm, it seems to me that “at the time that” means just about the same as “while”, although while has slightly broader usage. That, coupled with the similarity in form, makes it most likely that Gothic miþþanei and the others are the same word/phrase. Also, although miþ governs dative in Gothic, it presumably governed instrumental in Proto-Germanic (where it is *þanō in our reconstruction). A fossilized prepositional phrase is quite plausible, especially if it has become idiomatic, and what’s to prevent 𐌴𐌹 (ei) to be attached to that? I think it’s likelier than the preposition miþ being directly attached to the adverb; of course it might be hard, even for a native speaker, to tell the difference.