Here’s the short version: no.
Truly, this is a post I’ve been mulling over off and on for roughly three and a half years, although it may be more accurate to say its a concept I’ve been mulling over for that space of time. It isn’t always on my mind (it’d be exhausting if it were, truly, although I think I would’ve arrived at something cogent sooner had I spent more conscious time upon it before shuffling along to whatever struck me next), but its been there, lurking, waiting for something to raise it anew. Is Utena a magical girl? isn’t the question – I already knew that my answer as “no”. Instead, my question was – but if she isn’t a magical girl, why?
This is a tricky thing to defend, because RGU is clearly in part a response to the magical girl genre, even as it is also a larger response to ideas about gender performance and gender roles, the budding of adolescence, and social expectations about roles played more generally. Actually, I sort of wonder what RGU isn’t a response to – its easy, certainly, to pick out highly specific things it isn’t addressing directly (monster truck rallies! the wastefulness of disposable chopsticks! the Franco-Prussian War!), but harder to say what aspect(s) of human society, and the broader things that come out of that, it isn’t. Granted, some of this is due to Ikuhara’s deliberate obfuscation of questioning by fans, as well as the fact that we know that some things dropped in are meant to cloud attempts to define, but then we say, “Oh, well it clearly isn’t reacting to Japanese politics at all!” only to then think, “But, wait, Ikuhara wanted J.A. Seazer, a musician who only composed music for one other show, to compose for RGU because he became a fan of his music during the student revolutionary moments of the 60’s… so maybe it does on some level relate?”.
I digress fairly heavily, though. Back to my original argument – Utena isn’t a magical girl. Her story may be influenced by magical girl stories, and it may trade in some similar visuals, but she isn’t one, and I’ve never considered her one. It took ages for me to finally unravel why I do not, but now that I’ve done so, it seems to startlingly clear and obvious. Utena isn’t a magical girl because Utena never controls her own magic, and it is only when she shoves it aside and makes her efforts wholly under her own strength and abilities, not utilizing powers from Dios, that she truly triumphs. Sure, she beats the other duelists throughout with the sword of Dios, but all of these duels are merely dances in the palm of Akio, who believes Utena his best chance to get what he himself wants.
Utena doesn’t have her own magic, because for all her wielding of the sword, she can never invoke its magic truly of her own. Anthy controls the dueling arena, and Akio additionally does so through Anthy. Utena can climb the stairs or take the elevator, but the changes that occurs between then and the start of the duel come about because Anthy invokes magic. Even during the arcs where Utena draws the sword herself, it is only because Anthy allows her to. And Utena is only allowed to have the sword as long as Akio finds it of use to his own goals. I am reminded of Audre Lorde’s line, “For the master’s tools will never be used to dismantle the master’s house.” It is only when she repudiates the entire magical system that Utena is able to break free of it, and enable Anthy to do the same.
So I do not consider Utena a magical girl because to me a magical girl must have control over her own magic (as well as the fact that she ultimately rejects the magical system in which she was operating). Even in “darker” magical girl shows like Magi Puella Madoka Magica, where there is deception involved in the granting of magical powers, we find that the girls themselves do have a potential to wholly own their power and disrupt the system, as evidenced by Madoka and, yes, even Homura (since without Homura’s extreme efforts, Madoka would’ve never had the built up raw karma to enact a wish such as she had).
It should be noted, though, that I’m speaking more to the modern conception of magical girls (i.e. ones in which magic and fighting go hand-in-hand) rather than the older style, in which magic more often wasn’t about defeating the bad guys but about having adventures in every day life (see: Fancy Lala, Minky Momo, Sally the Witch, Hime-chan’s Ribbon). The magic in those shows seems to be more narrowly confined in what it can do and how it can be applied by the users of it, although I don’t feel comfortable making carte blanche statements about them since I haven’t watched nearly as much of them as I have of fighting magical girl shows.
(On a last note, and as an aside, if anything, I would argue that Anthy comes much closer to being a magical girl than Utena does, as she demonstrates an ability to invoke magic by herself and in places additional to the Dueling Arena. That Anthy is also identified as a “witch” plays in with this, too, as historically any woman or girl utilizing magic when we don’t like her gets classed as such. Shifts to a less negative connotation for “witch” don’t really surface much until we get to The Wizard of Oz, which makes sense considering L. Frank Baum was a feminist. At the same time, Anthy is only able to become free herself by rejecting the magical system she was part of. But Anthy and magic, and her identification as a ‘witch’ is a whole other post that I may or may not get to someday.)
GAR GAR Stegosaurus 
Agreed, that Anthy feels closer to the idea of the magical girl. Utena felt oddly less in control of her fate like you mentioned even though she won the duels she never had the ability to “save” anyone until the end.
Utena, to me, is a magical girl, just not a straight/traditional magical girl. In particular, I would say it’s a deconstruction of the magical girl series. It has the basic type of plot that you would see in your average magical girl, as well as the character archetypes, but it puts its on spin on things, like you already mentioned. Like you have your dark magical girl, you can have your deconstruction of the magical girl series (like Eva to mecha anime). On a minor note, I personally feel it’s unfair to compare something like Madoka to Utena, since they’re from 2 completely different eras of anime w/ different standards (which you commented on), however, I do agree Utena can seem hard to classify.
Additionally, you mention that you believe a magical girl should have control over & wield her own power. Keeping this in mind, take CardCaptor Sakura into consideration. Assuming that it’s agreed CCS is a magical girl, like Utena, her power isn’t her own, it’s Clow Reed’s (& in some instances Shaoron), but she is allowed to wield it through other means (the sceptor, Clow Reed’s former familiars, & several other magical objects that were given to her but not *hers*). Matter of fact, one of the major issues w/ her being Clow’s successor of sorts/a magical girl is that she didn’t have enough magical power to energize her familiars, etc. Despite all this, you would still consider this a magical girl. Similarly, Utena, like Sakura, uses magical items/powers essentially on loan to her but not actually hers, yet one is considered a magical girl & one isn’t (just as an example).
I feel that since Utena is one of the few deconstruction series in the magical girl genre that really go “out there” from what’s expected of a mahou shoujou series, it would understandably seem like it’s not a MG, but I feel it is simply due to having too many similarities (character archetypes, motivations, etc.) to what you would find in other MG series at least at the time.