Sayoko Shinozaki from Code Geass, whose true badassitude is revealed mid-second season. According to the audio commentaries, there was an in-joke among the staff about Sayoko somehow secretly being "the strongest character" during production of the first season, and by the time of R2 the series creators liked the idea enough to make it canon by turning her into a ninja maid. Technically denied by herself. When Rolo calls her a ninja, she corrects him, and calls herself an SP - a reference to Japan's Police division dedicated to bodyguard duties, itself heavily based on the American Secret Service. She just happens to have weapons similar to those a ninja would use.
Rosarita Cisneros aka Roberta from Black Lagoon, who isn't as much a Ninja Maid, as she is a Terminator Maid. She doesn't just know kung fu — she's bloody invincible, and carrying enough weaponry in her maid uniform to depopulate a small country. Considering that she used to be the infamous "Bloodhound of Florencia", the most dangerous hitwoman from the FARC… Ditto her younger apprentice, Fabiola Iglesias.
It's heavily implied that the agency member Mori Sonou from The Melancholy of Haruhi Suzumiya is one of these. Though technically she only pretends to be a maid as part of her cover. She demonstrates her true badass colors in Haruhi-chan but considering the series' status…
In one episode the then-villainous Evangeline took control of several of the girls' minds, dressed them up like French maids and then used them to fight Negi, knowing that he wouldn't be able to apply his full power against them. At the time, it seemed like the mind-control had inexplicably given them badass ninja powers, but considering later events, perhaps not...
Chachamaru, Evangeline's Robot Girl servant, also knows kung fu.
Tsurara and Shizuku from Kamen no Maid Guy. The "ninja" part is very literal for these two.
Maria from Hayate the Combat Butler, although outshone by the other Battle Butlers, can more than hold her own in a fight. Maria is usually absent or finds a way to resolve conflict without fighting; it's often implied that she is more capable than Hayate. She also seems opposed◊ to being thought of as a ninja maid.
Fumi Himeno from Mai-HiME, complete with a scythe as her Element. Too bad she has an Heroic BSOD after being defeated and losing her powers.
Any and all Otome in Mai-Otome. Want to know just how much? Originally the show was going to be called Mai-✩MAiD.
Media from Pani Poni Dash!; She apparently thinks the maid uniform is just part of being someone's assistant.
Luciene and Marianne, Ryoko's maids directly imported from France in The Case Files of Yakushiji Ryoko. The former is a genius hacker, while the latter is a weapons specialist. Both kick copious amounts of ass.
Normally the maid in the ecchi OVA Labyrinth of Flames is a DojikkoIll Girl... but if you force the contents of her IV into her arm, she briefly turns into the ultimate ninja.
In the first episode of Najica Blitz Tactics the heroine must battle a house full of machinegun-toting, panty-flashing, lesbian maids.
Hazuki Sakurazaka of Nogizaka Haruka no Himitsu, who is capable of roofhopping and knocking men out, and if that's not enough, she still have her chainsaw on her repertoire. Her fellow maid Nanami Nanashiro seems to be this way as well, as she is also pretty handy with her hammer. But she is mostly relegated to support actions, in the anime at least.
Hungary. She's not a maid all the time, but still often shows up in a maid's outfit... and is very willing to use her spear and/or her frying pan to defend her husband Austria, as Prussia and France learned the hard way.
Some people speculate that Belarus might end up hitting this trope as well. Her outfit is similar to a maid uniform and she's hinted to be a Knife NutYandere, so we'll see...
Masahiro Shibata's Sarai revolves around mercenaries known as Battle Maids.
Vizen Bercourt from Iono the Fanatics. Not only is she the Head Sobame but she is also officially the most badass one of them all, e.g. able to scare a Professional Killer away just by standing there and smiling politely. Having just smashed said killer into a wall a few seconds earlier with her Dynamic Entry helped.
Mahoromatic's a Robot Girl who depowered herself (as well as drastically shortening her lifespan) solely to become a maid for the male protagonist. She had good reason, though: she killed Suguru's father in the war, and that deeply scarred her, thus she chose to be his Suguru's to make it up to the kid she orphaned.
Maylene from Black Butler seems pretty useless as a maid. On more than one occasion she has mixed up shoe polish for wood polish, among other things. However, she's also an amazingly efficient sniper. She doesn't even use a sniping-scope since she's apparently THAT far-sighted (one of the reasons she probably mixes up cleaning products). She keeps a few racks of rifles on the roof so she doesn't have to waste time re-loading, and she's once seen using said rifles as pistols to take down baddies. But of course, it is only natural that a servant of Phantomhive would be able to do that.
Hannah from season 2 is also one of these. Not only she's a maid, but she's actually a demon.
Virgo from Fairy Tail. Bonus points, she used to be used as an actual body guard.
Many characters from The Melancholy of Haruhi Suzumiya. For example, in this episode, during a movie, Tsuruya decides to fight a monster from said movie, which turns out to be Mori, and then, Mori proceeds to knock out Tsuruya with a HUGEearthquakekick.
In the Christmas episode, Nagato traps the escaping "Santa."note And Nagato only used a very wide net.
With a manga called Maid War Chronicles it's pretty obvious that it's built on this trope. At first only Cocao, the lead, seems to truly fit it, but more and more maids are showing Hidden Depths...and some wicked Bad Ass skills.
Bleach: A flashback back arc reveals that the mixed-blood Katagiri was introduced into the pure-blood Ishida family when she and Uryuu's father Ryuuken were very young children to become Ryuuken's personal servant and his personal bodyguard. She is an excellent Quincy warrior who is Ryuuken's first choice as battle partner. She is eventually revealed to be Uryuu's Missing Mom and a Posthumous Character as she suffered a Cruel and Unusual Deathcaused by the same thing that caused the death of Ichigo's mother.
Mina Tepes' maids in Dance in the Vampire Bund double as her bodyguards. They don't know kung fu specifically, but given they're all vampires, they don't exactly need to.
Beelzebub has the wetnurses, including Hilda, one of the main characters. They are not ninjas, they are demons! Though, Hilda and Yolda have weird weapons, as Hilda has an umbrella sword and Yolda has a broom...
In Problem Children are Coming from Another World, aren't they?, Leticia Draculea is a powerful vampire knight who got captured by the rival community Perseus and was saved by the titular problem children. They want her to become their maid which she gladly accepts - after all she was spared a Fate Worse than Death as a Sex Slave thanks to them. This has the added bonus that not many people would suspect her (being a maid) to actually BE Leticia but rather a look-alike and doubly gives the advantage of having a good reason to have her around at all times.
Empowered features Maidman, a strapping male Ninja Maid.
In the alternate universe of Mutant XHavok employed none other than Elektra as a nanny for his son.
Shinji And Warhammer 40 K: Rei has come to regularly wear a maid suit when in her lord and master personal god Shinji's place of residence, keeps it in pristine order, and has inspired sufficient mortal terror amongst the Yakuza for them to offer him tribute on a regular basis. As for Bodyguard Crush, the term is far too limited.
One shows up in a side story to A Brief History of Equestria. And like any true ninja, not even the audience realizes what she is until it's too late.
In the third Pirates of the Caribbean movie Shao Feng's meek maids, Lian and Park, instantly turn badass when the East Indian Trading Company attacks his lair.
Lacey, Patience's maid, in Robin Hobb's Farseer Trilogy.
In The Princess Series Talia is one of the top secret agents for Queen Bea. She is highly trained martial artist whose abilities are enhanced by fairy magic. Her cover is that of a simple palace servant.
In "Exposed", an episode of the British sci-fi series UFO, Paul Foster makes a threatening move towards Dr. Jackson and finds himself caught in a judo hold by his beautiful Oriental servant. Jackson then coolly remarks: "Yes Mr. Foster, things are not always what they seem."
Akihabara@DEEP's Akira is a Maid Cafe waitress by day, professional cage-fighter by night. Once her otaku friends build a website for her, her popularity at the cafe skyrockets.
Luka in Episode 6 of Kaizoku Sentai Gokaiger, in which she goes undercover as a Meido in a fancy mansion. When a Zangyack invades it looking for the episode's MacGuffin, she uses her fighting ability to drive him away.
Shae from Game of Thrones. In the books, Shae is more of an innocent ingénue, and while she's still a maid, she has little insight into what's really going on around her. However, the TV series changes this significantly; she's still a handmaiden (and whore), but she's also very adept at lying, has a good eye for what makes people tick (and how to exploit it), and is a bit of a Knife Nut. She goes out of her way to protect Sansa Stark several times while she's in her care, even staring down Sandor Clegane and Ilyn Payne, both trained killers nearly twice her size.
Alcina from Endgame finds evidence, takes out hitmen, and makes sure your towels are extra fluffy.
In The Pink Panther, Inspector Clouseau's maid is a trained ninja. They spar regularly.
Iroha from Samurai Shodown. Particularly noticeable for looking almost exactly like what comes to mind when thinking of the term "Ninja Maid": she wears what is essentially a cross between traditional Japanese garb and the stereotypically skimpy French-maid costume.
With the right DLC, you can make one of these in the Soulcalibur IV and Soul Calibur V character creator.
While fetching the Dragon Tooth Sword in Deus Ex, JC finds it guarded by a maid. That promptly starts emptying clips on him.
Castlevania - Ninja Maids are a recurring enemy in the series.
They're called Persephone in Castlevania: Portrait of Ruin, and some of them have vacuum cleaners - which cause Charlotte to let out an embarrassed yelp if they catch her skirt.
They're also in the Castlevania: Chronicles of Sorrow duoogy, and their vacuums are their soul power. And they can be used to catch the skirts of Student Witches or the Persephones themselves. But those are more of the Kung Fu Maids.
The real Ninja Maids appeared in the Castlevania for X68000 (later ported to Ps1 as Castlevania Chronicles) in the final level, and some of them turned into Zombie Maids after death.
Melty Blood - Kohaku and Hisui got a maid-upgrade from Normal to Ninja. Kohaku in particular becomes faster than almost any other character in the game, including superhumanly fast vampires, and gets a hidden katana inside her broom. In the Tsukihime manga, Kohaku has a truly impressive all black meido outfit, for accompanying Akiha on less orthodox jobs. This is viewable in the original game; if you "Push yourself to see Arcueid," in the Arcueid route you get a Bad Ending where Kohaku wears this outfit.
Sakuya Izayoi of the Scarlet Devil Mansion from Embodiment of Scarlet Devil, capable of throwing dozens, if not hundreds, of knives at her foes at an instant. How she manages to carry them all is probably connected to her space-time-manipulation abilities.
ZUN stated once that Sakuya doesn't actually need that many knives (though she owns 'many), she simply collects the ones she already threw and uses them again with her Time Stands Still ability.
Shizune from Izuna 2 was sent overseas where she became the maid of the game's Big Bad. After she's reunited with her Ninja Cool Big Sis Shino and joins the player's party, she uses the same ninja tools that everybody else does.
Bloody Marie from Skullgirls is an odd case as instead of being a maid who just happens to know how to fight, she incorporates her job as a maid into her fighting style. Her main weapon, for instance, is a demonic vacuum cleaner.
Kuon of My Girlfriend Is the President is a unique example because despite being a hyper-competent bodyguard to Irina her specialty is not in bladed weaponry, throwing weaponry, or even melee. Rather she specializes in firearms and grenades. Lots and lots of grenades.◊ Though she does tend to be good at sneaking up on people and popping out of nowhere.
Lampshaded in Castlevina RPG's CVRPG Meets the TMNT arc. Darkmoom seems to have trouble realizing that not all Ninjas are maids.
Mecha Maid in the superhero comic Spinnerette combines this trope with Robot Maid since she's a ninja maid in a powered battlesuit. She even cites Mahoromatic as an inspiration.
Subverted, sort of, in a bit of Errant Story backstory that's important to the main plot: a standard Little Old Lady maid, whose main concern seems to be her aching feet, turns assassin. Her main weapon is a gun, but she still manages a nifty ninja jump — after the hand that fired the gun is cut off.
Amusingly justified example in The Order of the Stick, as one of the restaurant waiters is putting herself through ninja school on the side, and needs her restaurant job to pay the bills.
The filk song On Top of the Wall, whose narrator declares that she's "normally a scullery maid" but when the castle in which she works is attacked, she sings, "I'm up on top of the wall looking down on the raiders and the only source of comfort I can find is this large pot of oil, which I've just begun to boil. I've been cooking up on top of the wall."
While not as awesome as the Assassin's Creed's versions, hashshashins (assassins), their real life counterparts often disguised themselves as servants to deliver poisons or backstabs to their targets.
Despite the trope name, the word Ninja refers exclusively to males in this line of work. Women who take up the same career path are properly called Kunoichi (pronounced ku-NOI-chi) instead. However, the word Kunoichi has strong sexual connotations, so overall the older word Shinobi is prefered when refering to all ninja.
While not Ninja per se or as common as their male counterparts, in general if you were rich, you tended to attract enemies. Which meant that if you wanted to stay rich (or alive), it generally paid to have your house staff capable of doubling as home defense, including the women. The general societal obligation to defend one's employer also helped.