The issue with CERO seems to be that they don't like upskirt shots or any outfit that allows for an upskirt shot, rather than sexiness or breasts. During Smash 4, Sakurai and his team had issues with CERO simply because CERO thought Palutena, who is far tamer than Mai, they thought the slit in her dress was showing a bit too much to allow for a up shot and they had to stitch up the slit a good amount before getting the Okay. No one in the West noticed because this was only in Japan.
So it's hardly because of sexiness, as Samus' and Shulk's Alternate costumes and Bayonetta exist in Smash. They seem to get the Okay from CERO because they don't have underwear to show. CERO doesn't appear to have any issue with suits, shorts and whatnot. Meanwhile, Palutena and Female Corrin were sniped because their outfits could show underwear(especially in the case of Female Corrin, who's panties were outright exposed).
When you look at Mai, it's easy to understand why they had trouble with her, although it's not something simple like sexiness. Alot of people assume she would do her fighting pose that exposes her breasts when she has plenty of other poses where she's very tame. Like this one here:
https://vignette.wikia.nocookie.net...iranui..jpg/revision/latest?cb=20110903030152
As you can see in this one, she's not flaunting her breasts like her fighting pose. Heck, she's hardly even exposed aside from her legs, similarly to Lyn from Fire Emblem when summoned from the Assist Trophy. It's even possible that when they tried to put Mai in the game, they had her in a very tame pose like this one. If that's the case, her breasts and "sexiness" were far from an issue. But by the looks of it, despite having a tame pose and making it impossible to see her panties during gameplay,
UNLESS people directly tried to look for them, CERO simply had the issue at the idea of a character showing panties, even if gameplay wise they are never ever seen.
Considering Sakurai's love of SNK, that outfit is Mai's iconic look that she's had for more than 15 years that putting her in anything else probably felt like a fan disservice. SNK did try to give her a different look in one of the other Fatal Fury games, but that was quickly discarded and she was put back into her previous look. Sakurai may have fought to try to keep the iconic look while keeping the A rating, but CERO was too stubborn to budge just because she could show her panties.
If Mai was going to be a playable character, Sakurai certainly would've found a way to get her in, but ultimately, she was just simply going to be a background element and apparently, that was enough to make the choice of simply not putting her in if they couldn't get her in with her iconic look.