"If Air barriers were infinitely strong then why did it take so many Aes Sedai to create the barrier to fend off the Shaido?"

Maybe because each Sister could only make a barrier sufficient to cover a certain area, and due to this size limit and the fact that they were under attack, it took multiple Sisters to erect defenses.

"It would be helpful if one Aes Sedai could encircle the whole area but clearly they couldn't and needed a combined effort."

I want to note that the Asha'man ran into this problem - when they created and raised their barrier, a single Asha'man couldn't generate a barrier surrounding everyone - each had to make a "piece", push them together, and then raise them in on concentrated effort.

"We've also seen the Aes Sedai link to a circle of 13 when they thought Sammael was attacking Salidar, and they said they could stop a 'herd of charging bulls'."

This implies an attack IMHO. The example you quote is somewhat like comparing a boxer's ability to punch and knock out a single opponent versus fighting multiple opponents at once. For example, the club of Air Nynaeve used to drive off the pickpocket that hit Elayne with a cudgel would not be able to stop a herd of charging bulls - she could only hit one or a couple, and not a herd, since even the strongest channelers have a limit (which is why even Rand has never been shown to be able to blow away entire armies with a single attack until he gained Callandor). But a Circle of 13 could generate the same effect with more potency. The key point is, though, that the effect of hardening the air is still possible...but the quantity of opponents/targets and the size of the area that can be affected is determined by how much area your weaves of Air can take up, which is determined by your talents and your inherent strength with the Power.

"We've seen that lightning strikes barriers and needs a certain amount of strength to resist it. It may be power-wrought but it is more the product of a weave than a weave its self, and can kill Mat despite his medallion. Thus Rand, and later Cadsuane describe needing a great deal of the Power to deflect the attack."

I think a key point about this is one of RJ's earlier notes about Power-generated effects actions on each other (I wish we still had the One Power FAQ!) - basically, if a stronger channeler attacks a weaker channeler's effect, the amount of backlash the weaker channeler feels can be sufficient to kill or burn them out. Notice that Cadsuane didn't say her protective barrier was lessening in it's ability to defend the group - she said she had to use the full amount of Power she could generate with her angreal to counter the lightnings of a type she had never seen attacking it. Thus this more of an issue of Cadsuane needing enough Power to match the attack or her effect would be canceled out - it is more of a question of "all or nothing" versus resistance...either she could generate enough Power and push it into her shield to resist the lightning bolt or her shield would be destroyed and she would possibly be knocked unconscious or killed.

"I'm quite sure an air barrier is the same. An average female can probably deflect an enormous force, so it would take incredible force to break it - maybe too much for any man. But it is possible, and I think it's been shown already."

I don't think so - I think what happened in the Black Ajah scene was that Lan surprised them since he was close enough to enter their barrier unseen, the Sisters tried to weave something but he moved too fast for it to be completed, and then they smacked him away with Air. And this is not even taking into account that it may depend on the effect you generate - perhaps a net of Air can be forced apart, but a web, cocoon, wrap or solid grip of Air cannot. Weaves are not identical across each channeler, and there are a number of variables to consider.