Despite the guff that the supernatural romance genre gets these days (especially those directed towards the YA crowd), the idea of a supernatural entity coming down from on high to fall in love and badoinka-doink a human isn't a new concept by any stretch of the imagination. From the grigori "marrying" human women to Zeus hankying the panky across Greek mythology, people have been into the idea of supernatural creatures seducing (or being seduced by) mere mortals since the first person looked up at the moon and thought, "Hey. I wonder if anyone's banged that?"
That being said, there is a difference between a Magical Girlfriend and a supernaturally-inclined female character who happens to be in a relationship.
The Magical Girlfriend is a character subtype of the Manic Pixie Dream Girl wherein the aforementioned manic pixie might actually be a pixie. She might also be a robot, an angel, a goddess, a dragon, a witch, a demon, a genie, a mermaid, a baby mermaid, a greek-goddess-alien-thing, a princess from a magical land, a zombie, a witch, a witch, a witch, a watery tart, the queen of the fairies, a statue come to life, a mannequin come to life, a barbie doll come to life--
You get the picture.
Unlike the MPDG, who is a character type that can appear in multiple forms and across different genres/plot types, the Magical Girlfriend tends to have a more regular pattern to her and her relationships. This brand of story also tends to be aimed at adolescent audiences (especially in anime) and serve as a kind of wish fulfillment fantasy.
The main protagonist, with whom the audience is meant to sympathize, is still a down on his luck kind of guy who's just had a heartbreak, or he's moved to a new town and is out of sorts, or he's awkward--whatever. He's feeling down, but he's genuinely a good person, and suddenly a perfect, literally-too-good-to-be-true woman drops into his lap and changes his life.
If played straight, she'll fall almost immediately in love with him and be determined in a naive sort of way to solve all of his problems-- which may or may not cause more problems. In the anime versions of these stories, a lot of conflict (or what passes for conflict) comes from the girl's family/history coming to the surface. It turns out your robot girlfriend escaped from the institute that created her, or that you'll now have to impress the family of your celestial goddess girlfriend who don't much care for her dating a human, or, worst of all, you'll have to meet and compete with her ex. Expect there to be rivals in love-- both for her love, and also for the male protagonist, who despite earlier not having any luck with the ladies will suddenly find a host of evil demonesses or goddesses throwing themselves at him-- either to hurt his true lady love or because they genuinely are amused and impressed by the Nice Guy mortal that their sister/rival/archnemeses has found. Expect their love interests to blame the male protagonist for this and come around to beat him up as well.
In the western versions, the conflict usually arises from somebody trying to capture or expose the Magical Girlfriend E.T. style, and the couple has to escape or defeat them before being allowed to live happily ever after.
Like the Manic Pixie Dream Girl trope, this one is also getting a trend of reversing the roles and having a Magical Boyfriend who fits the Magical Girl characteristics (devoted, magical, naive, endlessly optimistic, "safe", etc.). This kind of gender flipping is more noticeable in the anime version of the trope, as those tend to be longer stories (an entire manga series/anime season), and also have more steps to their formula for said shows/books to hit on, thus driving home that-- yes, this is a Magical Boyfriend as opposed to a boyfriend-that-is-magical. This is also where it overlaps with the Supernatural Romance genre, especially the ones directed at the YA audience, which typically involves a female human character having a relationship with a supernatural male character, but usually won't follow the specific anime formula.
It should also be noted that just because a work is from a female point of view doesn't mean it's also not a magical Girlfriend Story. Bethany from those god-awful Halo books about angels is a Magical Girlfriend, even though she's the narrator and main character; she spends the entire novel mooning over her human boyfriend.
Again, a Magical Girlfriend is different from "a girlfriend who is magical." There is a far cry between Sakura from Cardcaptors, who is a Magical Girl who gets into a relationship (eventually), but is not a Magical Girlfriend, and Belldandy from Oh My Goddess! who is considered to be the quintessential Magical Girlfriend.
On the Western sides of things, the protagonist from Blood and Chocolate is a werewolf who dates a human, but she's not a Magical Girlfriend because she's not mindlessly devoted to her man, and in fact has a lot of other plot issues going on and is a (mostly) fully developed character in her own right. Same with Angua from Discworld, who is also a fully-developed werewolf female character who is in a relationship with a human. On the flip side, Madison from Splash is a more traditional Western Magical Girlfriend.
It should be noted that the Magical Girl genre of anime/manga has nothing to do with the Magical Girlfriend genre unless the Magical Girlfriend in question happens to be a Magical Girl as her quirk.