Okay, here are the reasons.
When first introduced, Mr. Mime's Japanese name was バリヤード, pronounced ba.ri.ya-do. Pretty obviously, its name means barrier, a reference to its mime skills and the most common & well known mime of invisible walls. So originally, the designers of バリヤード never intended it to be gender specific, unlike examples such as Sawk. That's why バリヤード has a 50/50 gender ratio. Only when it was given an English (and most other European) name did the gender confusion occur. Additionally, gender didn't arrive in the games until Gen II, so no Pokemon even had a gender apart from NidoranM/F.
As for Gardevoir, it's not meant to be ultra feminine. Its design is based upon a knight wearing a cape, as per its Japanese name, サーナイトpronounced sa-na.i-to, i.e. Sir Knight. So the question should really be, "why are there female Gardevoir?" Its designers only compounded the confusion by introducing Gallade, which fans (mis)interpreted as an ultra-masculine form of Kirlia. Then Gardevoir was made even more confusing with Mega-Gardevoir, which was again (mis)interpreted by fans as wearing a wedding dress and dubbed (in poor taste) "Mega-waifu". Gardevoir was supposed to be an elegant knight based upon the the idea of chivalric tradition from the European middle ages, and/or influenced by the operatic portrayal of this idea. It's supposed to be some form of personal guardian, as indicated by its Pokedex:
>It will try to guard its trusted Trainer with its life. It has the ability to see the future. (Diamond)
>It unleashes psychokinetic energy at full power when protecting a Trainer it has bonded closely with. (HGSS)
>To protect its Trainer, it will expend all its psychic power to create a small black hole. (X)
So while Gardevoir does have a gender confusing name in Japanese, it was never meant to be a solely female species, unlike Jynx or Froslass. However, some fans projected their Pokefillia fantasies upon Gardevoir, making the entire species ultra feminine, when it was really supposed to be an elegant masculine knight. As Tamashii Hiroka puts it, "sorry, but your waifu is kind of a dude".
Tamashii's video, where she talks about overrated Pokemon and Gardevoir is #9. Also explains the projections it has from the Pokefillia community.