I was thinking that Power Toyohime might be a decent counter. Power Toyohime is immune to Spirit Rock Dance, and takes reduced damage from her warrior-type attacks. She has enough bulk to take her wind-type attacks as well (probably, I haven't tested it myself yet) and can OHKO with her own wind-type moves (Power Aya has a weakness to wind due to warrior typing). Power Aya also has access to Lightning Speed (basically Volt-Switch), allowing her to OHKO Power Toyohime while escaping, however.
To be a proper counter, a puppet has to be able to take not one, but two of Power Aya's attacks and survive, one on the switch and again on the second turn because there is a good chance she'll be slower than Aya. (that assumes Power Aya will even stay in against anything that could threaten her. She can simply use Lightning Speed to switch out and damage them back in the process).
Power Aya has access to Spirit Rock Dance, essentially preventing steel and electric-types from switching in that would normally wall Aya. Not all steel-types are weak to warrior (Speed Youmu, for example, is immune). When her power points are properly invested, Power Aya has a focus attack on par with uninvested base 130-power sweepers, making switching in on any attack, even neutral hits, a risky gambit. She also is practically immune to stall due to her attacks' high use count, and substitutes are similarly useless due to multi-hits.
PAya grants momentum from her mere presence. If she is chosen as the lead puppet, chances are the other player will be scrambling to counter her throughout the match. The only puppets that act as a firm counter to her would be faster sweepers which she cannot use Lightning Speed to escape or her speed to OHKO first (but must be used as revenge killers or leads), or Defense Shinyoku who can tank anything Aya can send at her and set up Genbu and nullify her speed advantage. She has an answer to all three of her weaknesses, and gains STAB against one of them.
PS: I'm sorry if I derailed the conversation. Defeating PAya is just something on my mind lately, so please forgive me ^_^"
PPS: I found a puppet that completely counters Power Aya, at least in terms of type advantage. Speed Ellen with Air Cushion ability resists or is immune to all of Power Aya's moves.