I thought it was “aioli” in French. The Spanish “allioli,” as I know it, is an emulsion of just garlic and olive oil made in a mortar. The Provencal “aioli” has the addition of egg yolk, the defining characteristic of mayonnaise sauces. My guess would be the inspiration for aioli is quite obviously Catalonian, but the yolk and subsequence mayonnaise-like emulsion is the French twist.
Hence your user name. 
The jars in my supermarket (French, of course, I mean, why buy in Switzerland or Germany when you actually sleep in France?) say allioli or even all-i-oli with the dashes. If it’s made with egg, then a Catalan would claim it’s not real allioli, but a lot of other people who have acquired the name recently use it for garlic mayo… which is what you describe, yes.
Was that cook in Mahón french? Dunnow. All I can do is give “my” version as I got it from the Spanish Academies of the Language, Catalan tradition, Spanish tradition and an observation of “the strange things that happen to cookstuffs as they become popular” (for example, salsa brava moving from being real mayo with red pepper, to being a mixture of bottled-mayo and ketchup).
Are you certain that one of those products hasn’t completely singed your taste buds? Maybe that explains it. 
No explanation as to whether the Duke’s personal chef was French or Spanish, but I would assume French.
I’m surprised to hear that aioli is sold as “allioli” in France. I’ve only seen it as “aioli” myself, but I admit I was never paying that close attention to it. Here’s a jar of the French stuff.
As for the linguistic derivation of “aioli,” what if I told you “ai” means “garlic” and “oli” means “oil” in Occitan, a language mostly spoken in Southern France, although it does dip into a sliver of Spain and Italy?
I wouldn’t discount it, Balthisar.
But, seriously, I don’t think my experience is unique in this regard.
Really? Miracle Whip, from what I remember, has a different texture and much different taste from Hellman’s. Most notably, Miracle Whip is flavored with a bunch of stuff and has a more, I dunno, tart and tangy taste than typical mayo.
A brief hijack:
With your knowledge of sauces, is the military chef being asked by his commander to put some delicate sauce “to go” and shooting himself an urban legend?
The only time I can detect a difference is in a side-by-side taste test. If you just put one or the other in a sandwich or potato salad, I’d never know.
I would tell you that the similarities between Langue d’Oc and Catalan (which includes Provençal) is the reason why I specified they’re considered different languages 
Anyway, this thread was supposed to be about taste and recipes, not about linguistics… my apologies for the hijack. I won’t be posting again except if I remember to bring my camera in the next trip to the supermarket. I recall seeing several spellings; the “proper Catalan” ones struck me for the same reason as seeing sobrasada did last Monday: it’s not something I’d eat at home, but it’s a taste of home nonetheless.
Oh, don’t get me wrong. I don’t disbelieve you at all. It’s just that I’m more familiar with the aioli spelling of the garlic mayonnaise in France. I’m sure there’s aioli sold as “allioli” in France, but I’ve always been under the impression that “aioli” is how it’s more commonly referred to in France. And what I know as Catalan allioli is a little bit different that what we think of as aioli, which is more-or-less garlic mayonnaise.
Anyhow, somebody at Wikipedia seems to agree with me, although I do know I have seen Spanish allioli with egg yolks somewhere before.
edit: Ah, crap, my apologies. I somehow skipped over one of your posts, Nava where you do cover this. Please disregard.