Misoverheard would be a more probable neologism.
First, while overheard is a common concept over- as a prefix wouldn't retain the sense of eavesdropping if added to misheard. In the Oxford English Dictionary, "over-, prefix," the over- in overhear or oversee is sense 1.o in a long list of senses (1.a through 1.n, and all the entries afterward to 3d). This indicates that other meanings would easily interfere with your intended one, like being spatially or temporally over something or doing something too many times.
Second, mis- would preserve the sense of mistaken action when applied to overheard. In the OED your intended sense is the first entry listed:
a. Prefixed to verbs, with sense ‘badly’, ‘wrongly’, ‘perversely’, ‘mistakenly’, ‘amiss’.
Mis- commonly does this even today. I could say misclicked, for instance, to mean I mistakenly clicked, just like I can say I misoverheard to say I mistakenly overheard. Over coinages would make sense: I misliked a social media post or mistweeted an update. However, saying I overclicked, overliked, or overtweeted would more likely lead people to think that I had clicked, liked, or tweeted too many times for a given function.
Finally, just to confirm which sense people go with more often, a Google search illustrates that misoverheard is occasionally used or coined with about 1890 results as of this writing, whereas overmisheard has 9 results, one of which is this question. That suggests misoverheard is far more likely to be understood in use.