Maya's main Artifice is her constant spamming of Evade. This functionally allows her to evade two hits per turn.
Her secondary Artifices are her HP Regeneration and her 4-hit Act 2. Her Regeneration penalises dragging on the battle for too long, while her 4-hit Act 2 can easily remove evades and fortitude.
All attackers, and essentially anyone who isn't a tank, ought to have a perfect aim memoir equipped. These are the most common memoirs you will come across that can be used, though there are, of course, other ones. 3★ Stretching Help...? is the ideal memoir for your attackers if max bound broken, but the ad-gacha version will suffice.
3★ Martial and Dramatic Arts
Ad-gacha (DMG + Perfect Aim)3★ Stretching Help...?
(Effective Element DMG + Perfect Aim)3★ Idle Banter for Two
(DMG + Perfect Aim)3★ Present for the Detective
(DMG Received Down + Perfect Aim)Her Normal Act 2 can be exploited to your advantage through the mechanic known as Counterheal. If Maya uses her Act 2 against a Flower tank with counterheal, they will heal up almost 40% of their HP, enabling them to survive longer and carry you to victory. Note that only girls that can give counterheal within 2AP are acceptable. This means, however, that you have to accept that Maya will regenerate a substantial amount of health. Alternatively, you can use a hyper-offensive team that does not employ counterheal and simply smites Maya into dust.
1) Healing is for the weak.
As an old boss, Maya's HP pool is very pathetic compared to the current crop of damage dealers. Punching through her with sheer brute force is the fastest way to deal with her.
1) Standard Full Team
The cornerstones of this team are one counterhealer (preferably Arthur Karen) and two Flower tanks. At least one of the flower tanks must have a taunt ability. As Maya attacks the front 2 often, maintaining taunt allows the two flower tanks to go down separately instead of together. However, ensure that on the turn where you choose to cast counterheal, Maya is not taunted, and is not going to cast her CX. If Maya casts her CX, there is a possibility of her not using her ACT2, thus wasting the counterheal.
The front tank should be counterhealed 0-1 times, and the second tank should be counterhealed 1-2 times. The stronger your support and choice of counterhealer, the more leeway you have.
Between defending with taunts and desperately charging your counterhealer, you may not seem to do much damage, but do not despair. Your damage per turn ramps up significantly once your tanks are out of the picture.
1) One-hundred-and-one Home Runs
Awakened Mahiru, alone, can easily solo Maya, while on auto. This is due to the massive amounts of heals she has. To speed up the process, you can consider bringing fodder with offensive-based unit skills that boost Mahiru's damage, as well as using the 1st Anniversary Seisho Memoir, which also boosts Mahiru's damage.
Mahiru herself should use a Perfect Aim memoir as well.
2) Gawain's Poison
Taunt thrice and poison four times, then watch Maya die.