Proto-Germanic ancestor of meðan

miþþanei actually exists in Gothic, but it means "at the time that" and is composed of miþ (“with”) and þanei (“then (relative)”), the latter of which is formed from þan (“then, at that time”) + -ei (relative particle).

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.