She recovers extremely quickly after throwing a fan. I would only punish a fan with qcfx2+AC, to be safe. qcfx2+AC is so damn fast.
If she jumps, qcfx2+A/C is really good. It's invulnerable in the startup and as an anti air often gives you a wall-bounce combo.
Mai's air game is really annoying, I know this matchup all too well, but I actually find it in Shen's favor. If you can get past those annoying st.B, st.D pokes then you shouldn't have too much trouble. Mai lacks anti airs completely, so you can hop D pressure her pretty well.
Essentially to win the match you have to go into it with lots of meter.
If you ever see Clark doing hcf+B, try to get an EX grab out. It'll win. I also have trouble with this matchup though. Grapplers in general are a really tough situation for Shen. I guess it's because he needs to get into their throw range to start any of his damage, and that's not a place that most people want to be.