Actually in KOF XIII I would say she's a solid mid tier. She doesn't have the combos, true, but she more then makes up for it with agility. Her fans can match up with King's fireballs (except for the double super) just fine. Her pokes are the best in the game. Her CD attack in the air and ground is top tier, and her Neo Max is one of the few you can do raw and constantly connect just by judging the position of where the opponent jumps. If she had combos she would be completely broken with how easy you can set stuff up. The trick is if you prefer footsies if you like her or not.
Well, one sure can be annoying with Mai in KOF XIII. As you said she is all normals, and air CD, and NeoMAX (i don't agree with fireballs. King is far better in zoning). Her special moves are just BAD. The worst ones Mai never had before. Punshible, low damaging, no prior, bad hurtboxes, etc. That's why I said she's bad. She has combos in fact, but the problem is that you need a lot EX moves to combo, so Mai is an expensive character in therms of bars. Players usually prefer use Mai for her normals and save metter for other characters, or save metter for her NeoMAX. To be honest, that wasn't my playstyle. I used Mai as third character and I try to do many combos as i can, just because I enjoy playing her and I don't want to use her in a simple way. Some of my rivals were really surprised that Mai could do such combos! xDD But yes, I can understand that most of high level players use her like you say (if they use her..). But to me, she is still a low tier. What i like about Mai in XIII is her speed. Sure one of the most fast characters in XIII. She should be always like that. I hope she will be fast in XIV too.
@Shiranui_Ninja: it was announced that china will have a stage tho
Yes, it make sense, since China Team will be one of the protagonist teams in XIV story