Ahri is mostly strong due to the champions that do well against her being weakened.
Ahri used to be very weak to Syndra (extremely squishy versus Syndra's targeted R, if you didn't rush MR you got 100-0'd easily at 6). Syndra has seen some damage nerfs which helped Ahri though. Likewise as you mentioned LeBlanc got nerfed (or banned out). Ahri's worst matchups being removed made room for her to shine (so she was always strong, and got indirectly stronger through enemy nerfs).
I don't think she's OP, I actually think she's really balanced in that she actually makes a lot of real sacrifices to be a jack-of-all-trades. She truly is a master of none. Her mobility is good but not great (ultimate has a long cool down and Q MS isn't nearly as impactful as a dash would be). Her damage is moderate (no where near the burst of assassins or burst mages). Her CC is moderate-weak (a 0.75 second charm that has short range and is intercepted by minions, probably the weakest CC duration to difficulty-to-land CC in the game). Her kit works really well together to allow her to make plays (i.e. her R-E or F-E combo makes that difficult to land CC a lot easier) while simultaneously punishing her for misplaying / allows enemies to punish her if they outplay (she blows a huge cool down if her opponent dodges the E).
I can't think of any other champion that has to blow their ultimate or flash in order to go for a play that the enemy can avoid without flashing themselves. You won't dodge an Annie's F-R unless you F because it's instant, for example. On the other spectrum, Syndra won't R you until she's successfully landed the Q-W-E (or just has you low enough to kill). Most champions can hold on to their power until they're certain it will work, while Ahri has to take a real risk to go for her chance. I think that's a hell of a lot more balanced than the other stuff out there.
So the question really just comes down to numbers for me. I'm cool with the idea of nerfing her Q MS at early ranks so she doesn't have so much ability to dodge in lane (although it will take getting used to, as I love when a Blitz tries to invade and I Q him and the MS lets me outrange his hook, nerf it at all and I'll get caught!). My suggestion was to make it give less when going out and more when coming back (so it's equally good when kiting/fleeing but much worse when chasing). Her damage is too low for it to see nerfs, unless they nerf the early W damage and make it scale back up with ranks (i.e. force her to max W second so she can't get a more useful CC by giving charm a couple extra ranks first) (Bjergsen levelled charm to 2 at level 8 and 3 at level 10 before maxing W the last game he played her, for example).
Which isn't to say I think she needs nerfs. She's just a safe generalist pick that works with a lot of team comps, so players who stick with her are rewarded more than people who stick to other champions (as those champs have situations where they work much worse with certain team comps). That's not a fault of champion balance, it's a fault of it being more rewarding to main Ahri than another champion from a reliability perspective, which is just sort of "tough grapes, that's how it is". It's the benefit of playing a champion that offers a bit of everything.