Usually, this is attributed to the 12th century anglo-norman Chanson de Roland (text; easy text):
Li arcevesque cumencet la bataille.
Siet el cheval qu'il tolit a Grossaille,
Ço ert uns reis qu'l ocist en Denemarche.
Li destrers est e curanz e aates,
Piez ad copiez e les gambes ad plates,
Curte la quisse e la crupe bien large,
Lungs les costez e l'eschine ad ben halte,
Blanche la cue e la crignete jalne
Petites les oreilles, la teste tute falve;
Beste nen est nule ki encontre lui alge.
Li arcevesque brochet par tant grant vasselage:
Ne laisserat qu'Abisme nen asaillet;
Vait le ferir en l'escut amiracle:
So this cue comes from the Latin cauda/coda. This is most probably pronunced like a k. The two forms sound basically like kao-da vs. koda with some variation. In latin words beginning with the letter q are quite common I think, and mostly always followed with u. The pronunciation may(kw) or may not be different. What I imagine is they saw that and have some Scandinavian, Norman influences, so did they have some natural cue about that pronunciation? Or did they just try to copy it, especially if Latin was well perceived a language or historically relevant to some? Furthermore, maybe you have something akin to a preposition such as de, and then you would have had something like a koede de cheval for ponytail, which would be really aggravating. If you were to drop or shorten the last syllable, you would be left with cau/co; so how does a Norman language deal with that?? I speculate they must have transliterated it from Latin directly and dropped the last part, and eventually that was rejected - in French. It seems in Norman quisse was how cuisse is prononced today in French, so it's that kw sound, very much like qu in latin I suspect, again. You can't make queue with cue phonetically in French unless you were to rely on something else...
In the Historical section of this article in the Littré on queue, you see the Chanson example, then followed by examples with cöe(see also Trésor). Right away cue is gone, and it's now coe, a bit like coeur but without the last sound? Maybe that would have been slightly confusing? And ultimately what about cueillir, recueuil etc.... it becomes a bit crowded. So listen again to the Chanson: Rolans sis niez me coillit en haür. This "cueillir" is also quite different from modern French. So surely it was adapted for something that sounded different. And then all this disappears in the 15th. So it seems like it was idiomatic or somehow just worked phonetically in English, but didn't compute with what French was becoming in the 15th.
Norman influence(s) and Old French generally
Aside from the political influence Normandy exerted at a specific period in time, there is also value in briefly stating the historical context where the Norman language expresses itself initially:
Les nouveaux venus[anglo-scandinavian settlers, so maybe also this] vont exercer sur la langue vernaculaire une
influence limitée de substrat, notamment sur le vocabulaire (200 mots
tout au plus, issus du norrois ou du vieil anglais cf. tableau I) et
de manière plus anecdotique sur la phonétique.
This is just to show that generally some influences can carry other interferences over and that the ensuing result varies; how language changes may not be something linear or grounded on a specific mission; there might be opportunity, randomness, normative instruments, and of course history.
From the wikipedia article:
[...] si l'ancien français s'écrit presque comme il se prononce, les
graphies deviennent très vite archaïsantes. Par exemple, doté de
nombreuses diphtongues, il les représente directement : /eu/ se lit
donc [ew] et /oi/ [oj]. Mais les graphies restent figées alors que la
prononciation continue d'évoluer: /eu/ vaut [ew] au XIe siècle mais
[œu] au XIIe siècle et [œ] à partir du XIIIe siècle sans que la
graphie ne change réellement. [...]
En conclusion, il convient de comprendre que l'ancien français possède
une orthographe quasi-phonétique pratiquée avec un alphabet qui ne s'y
prête pas forcément, ce qui explique l'abondance de graphies
parallèles et les diverses solutions plus ou moins efficaces, tels les
digrammes, mais, surtout, dès que les prémices de l'orthographe, au
sens actuel, font leur apparition : l'écriture est en retard sur la
prononciation mais permet, par l'adoption de conventions, une
meilleure reconnaissance des constituants des mots.
Synthèse [...] la lecture des diphtongues graphiques est complexe car les diphtongues prononcées ont évolué beaucoup plus vite que la
graphie. On pourra retenir comme règle de lecture acceptable que les
diphtongues se sont monophtonguées après le XIIe siècle (passant soit
à une combinaison semi-consonne + voyelle soit à une voyelle seule.
Retenir aussi que oi se lit /we/ ou /wɛ/ et ue comme eu /œ/ ou /ø/ ;
A. So was there ever a motivation to make words more "straightforward" etc?1 I just think the French language asserted herself, in time, to find solutions on its own terms so to speak, so that the "system" would work. And then at some point in the 15th it stabilized in some respects, like explained in this Q&As, with indeed less reliance in this very case on that original latin anglo-norman construction for cue.
1. Take the word hue in English which is shorter than color, and from the same era; yet the latter is what is casually used today(maybe that's a ticket for a Q. on ELU.).